# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1207968 | segfault_ikuyo | Race (IOI11_race) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define pii pair<int,int>
const int maxn=2*1e5+5;
const int maxk=1e6+5;
vector<pii> adj[maxn];
pii path[maxk];
int vis[maxn], siz[maxn];
int n,k,a,b,c;
int ans;
queue<pii> q;
int dfssiz(int x, int pre){
int sizz=1;
for(pii i:adj[x]){
if(i.first==pre||vis[i.first]) continue;
sizz+=dfssiz(i.first,x);
}
siz[x]=sizz;
//cout << x << '-' << siz[x] << '\n';
return sizz;
}
int dfsget(int x, int pre, int c){
for(pii i:adj[x]){
if(i.first==pre||vis[i.first]) continue;
if(siz[i.first]>=siz[c]/2) {
return dfsget(i.first,x,c);
}
}
return x;
}
void dfssolve(int x, int pre, int d, int dd, int c){
if(dd>k) return;
if(dd==k){
ans=min(ans,d);
return;
}
if(path[k-dd].second==c){
ans=min(ans,path[k-dd].first+d);
}
for(pii i:adj[x]){
if(i.first==pre||vis[i.first]) continue;
dfssolve(i.first,x,d+1,dd+i.second,c);
}
q.push({d,dd});
}
int getcentroid(int x){
dfssiz(x,-1);
return dfsget(x,-1,x);
}
void solve(int x){
if(vis[x]) return;
int c=getcentroid(x);
path[0]={0,c};
pii cur;
for(pii i:adj[c]){
if(vis[i.first]) continue;
//q.clear();
dfssolve(i.first,c,1,i.second,c);
while(!q.empty()){
cur=q.front();
q.pop();
if(path[cur.second].second!=c) path[cur.second]={cur.first,c};
else path[cur.second].first=min(cur.first,path[cur.second].first);
}
}
vis[c]=1;
for(pii i:adj[c]){
if(vis[i.first]) continue;
solve(i.first);
}
}
signed main(){
cin.tie(0);
ios_base::sync_with_stdio(0);
memset(path,0xff,sizeof(path));
cin >> n >> k;
ans=LLONG_MAX;
for(int i=0;i<n-1;i++){
cin >> a >> b >> c;
adj[a].pb({b,c});
adj[b].pb({a,c});
}
solve(0);
if(ans==LLONG_MAX) ans=-1;
cout << ans << '\n';
return 0;
}