| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1315903 | javkhlantogs | 경주 (Race) (IOI11_race) | C++20 | 0 ms | 0 KiB |
#include<bits/stdc++.h>
#define ll long long
#define pll pair<ll,ll>
using namespace std;
vector<vector<pll>> e;
vector<ll> sz;
vector<bool> rem;
map<ll,ll> cnt;
ll ans=1e9,k;
ll getsz(ll u,ll p){
sz[u]=1;
for(auto v:e[u]){
if(v.first==p or rem[v.first]==1) continue;
sz[u]+=getsz(v.first,u);
}
return sz[u];
}
ll getct(ll u,ll p,ll n){
for(auto v:e[u]){
if(v.first==p or rem[v.first]==1) continue;
if(sz[v.first]>n/2) return getct(v.first,u,n);
}
return u;
}
void getans(ll u,ll p,ll d,ll l){
if(l>k) return;
if(cnt.find(k-l)!=cnt.end()) ans=min(ans,d+cnt[k-l]);
for(auto v:e[u]){
if(v.first==p or rem[v.first]==1) continue;
getans(v.first,u,d+1,l+v.second);
}
}
void update(ll u,ll p,ll d,ll l){
if(l>k) return;
if(cnt[l]>d or cnt[l]==0) cnt[l]=d;
for(auto v:e[u]){
if(v.first==p or rem[v.first]==1) continue;
update(v.first,u,d+1,l+v.second);
}
}
void decompose(ll u){
getsz(u,u);
ll ct=getct(u,u,sz[u]);
rem[ct]=1;
cnt.clear();
cnt[0]=0;
for(auto v:e[ct]){
if(rem[v.first]==1) continue;
getans(v.first,u,1,v.second);
update(v.first,u,1,v.second);
}
for(auto v:e[ct]){
if(rem[v.first]==1) continue;
decompose(v.first);
}
}
int main(void){
ios::sync_with_stdio(0); cin.tie(0);
ll n,i,j,q;
cin>>n>>k;
e.resize(n+1);
sz.resize(n+1);
rem.resize(n+1,0);
vector<pll> h(n);
vector<ll> l(n);
for(i=0 ; i<n-1 ; i++) cin>>h[i].first>>h[i].second;
for(i=0 ; i<n-1 ; i++) cin>>l[i];
for(i=0 ; i<n-1 ; i++){
e[h[i].first].push_back({h[i].second,l[i]});
e[h[i].second].push_back({h[i].first,l[i]});
}
decompose(1);
if(ans!=1e9) cout<<ans<<"\n";
else cout<<-1<<"\n";
return 0;
}