//IOI 2011 Day1 Problem 2 Race
//Full solutions
#include "race.h"
#include <bits/stdc++.h>
using namespace std;
const int inf=1e6+9;
vector<pair<int,int> > v[inf],add;
bool blocked[inf];
int subtree[inf],level[inf],dis[inf],min_path[inf],parent[inf],n,k;
void dfs_size(int node,int par){
subtree[node]=1;
parent[node]=par;
for(auto o:v[node])
if(!blocked[o.first] && par!=o.first)
dfs_size(o.first,node),
subtree[node]+=subtree[o.first];
}
int dfs_add(int node,int l,int d,int par){
if(d>k)
return 1e9+9;
add.push_back(make_pair(l,d));
int ret=min_path[k-d]+l;
for(auto o:v[node])
if(o.first!=par && !blocked[o.first])
ret=min(ret,dfs_add(o.first,l+1,d+o.second,node));
return ret;
}
void dfs_remove(int node,int d,int par){
if(d>k)
return ;
min_path[d]=1e9+9;
for(auto o:v[node])
if(!blocked[o.first] && par!=o.first)
dfs_remove(o.first,d+o.second,node);
}
int solve(int centroid){
min_path[0]=0;
int ret=1e9+9;
for(auto o:v[centroid]){
if(blocked[o.first])
continue;
ret=min(ret,dfs_add(o.first,1,o.second,centroid));
while(!add.empty())
min_path[add.back().second]=min(min_path[add.back().second],add.back().first),
add.pop_back();
}
dfs_remove(centroid,0,-1);
return ret;
}
int create(int start){
dfs_size(start,-1);
int centroid=start,best=subtree[start];
queue<int> q;
q.push(start);
while(!q.empty()){
int u=q.front();
q.pop();
int sz=subtree[start]-subtree[u];
for(auto o:v[u])
if(!blocked[o.first] && parent[u]!=o.first)
sz=max(sz,subtree[o.first] ),q.push(o.first);
if(sz<best)
best=sz,centroid=u;
}
blocked[centroid]=1;
int ret=solve(centroid);
for(auto o:v[centroid])
if(!blocked[o.first])
ret=min( ret,create( o.first ) );
return ret;
}
int best_path(int N, int K, int H[][2], int L[]){
n=N;
k=K;
for(int i=0;i<=K;i++)
min_path[i]=1e9+9;
for(int i=0;i<N-1;i++){
int x=H[i][0],y=H[i][1],z=L[i];
v[x].push_back(make_pair(y,z));
v[y].push_back(make_pair(x,z));
}
int ret=create(0);
if(ret>N)
ret=-1;
return ret;
}
