#include #include #include using namespace std; typedef long long ll; vector G[200010]; ll sum[200010],mx1[200010],mx2[200010],a[200010]; void dfs1(int s,int p){ sum[s] += a[s]; for(int v:G[s]){ if(v==p) continue; dfs1(v,s); sum[s] += sum[v]; } } void dfs2(int s,int p){ ll ret = -100000000; for(int v:G[s]){ if(v==p) continue; dfs2(v,s); ret = max(ret,mx1[v]); } mx1[s] = ret + 1; if(a[s]) mx1[s] = max(mx1[s],0LL); } int init = 0; ll dfs3(int s,int p){ init++; for(int v:G[s]){ if(v==p || sum[v]==0) continue; dfs3(v,s); } } ll ans[200010]; void reroot1(int s,int p,ll now,ll cnt){ ans[s] = now; for(int v:G[s]){ if(v==p) continue; if(sum[v]==0) reroot1(v,s,now + 2,cnt); else if(sum[v]==cnt) reroot1(v,s,now - 2,cnt); else reroot1(v,s,now,cnt); } } void reroot2(int s,int p,ll now){ mx2[s] = now; if(a[s]) mx2[s] = max(mx2[s],0LL); vector> vec; for(int v:G[s]){ if(v==p) continue; vec.push_back({mx1[v],v}); } sort(vec.begin(),vec.end()); if(vec.size()==0) return; if(vec.size()==1){ for(int v:G[s]){ if(v==p) continue; reroot2(v,s,mx2[s] + 1); } }else{ for(int v:G[s]){ if(v==p) continue; if(v==vec.back().second) reroot2(v,s,max(mx2[s] + 1,vec[vec.size() - 2].first + 2)); else reroot2(v,s,max(mx2[s] + 1,vec.back().first + 2)); } } } int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); int i,n,k; cin >> n >> k; for(i=0;i> u >> v; u--; v--; G[u].push_back(v); G[v].push_back(u); } for(i=0;i> x; x--; a[x]++; } dfs1(0,-1); dfs2(0,-1); dfs3(0,-1); init--; init *= 2; reroot1(0,-1,init,k); reroot2(0,-1,-1000000000); /*for(i=0;i