#include "factories.h" #include<bits/stdc++.h> using namespace std; #define ll long long #define ii pair<ll,ll> #define fir first #define sec second #define pb push_back const ll maxn=5e5; ll n; vector<ii>adj[maxn+2]; ll sub[maxn+2]; bool vis[maxn+2]; void dfs(ll cur,ll par){ sub[cur]=1; for(auto [x,di] : adj[cur]){ if(x==par)continue; if(vis[x]){ sub[x]=0; continue; } dfs(x,cur); sub[cur]+=sub[x]; } } ll centro(ll cur,ll par,ll sz){ for(auto [x,di] : adj[cur]){ if(x==par || vis[x])continue; if(sub[x]>=sz/2){ return centro(x,cur,sz); } } return cur; } vector<ii>anc[maxn+2]; void comp(ll cur,ll par,ll root,ll tot){ anc[cur].pb({tot,root}); for(auto [x,di] : adj[cur]){ if(x==par || vis[x])continue; comp(x,cur,root,tot+di); } } void solve(ll cur){ dfs(cur,0); ll root=centro(cur,0,sub[cur]); comp(root,0,root,0); vis[root]=true; for(auto [x,di] : adj[root]){ if(vis[x])continue; solve(x); } } ll dkt[maxn+2]; void Init(int N, int A[], int B[], int D[]) { n=N; for(int q=0;q<n-1;q++){ adj[A[q]].pb({B[q],D[q]}); adj[B[q]].pb({A[q],D[q]}); } solve(1); for(int q=0;q<N;q++)dkt[q]=1e18; } void update(ll idx){ for(auto [tot,root] : anc[idx]){ //cout<<idx<<" "<<tot<<" "<<root<<endl; dkt[root]=min(dkt[root],tot); } } void reset(ll idx){ for(auto [tot,root] : anc[idx]){ dkt[root]=1e18; } } ll query(ll idx){ ll ans=1e18; for(auto [tot,root] : anc[idx]){ //cout<<idx<<" "<<tot<<" "<<root<<" "<<dkt[root]<<endl; ans=min(ans,tot+dkt[root]); } return ans; } ll Query(int S, int X[], int T, int Y[]) { for(int q=0;q<S;q++){ update(X[q]); } ll ans=1e18; for(int q=0;q<T;q++){ ans=min(ans,query(Y[q])); } for(int q=0;q<S;q++){ reset(X[q]); } return ans; } // signed main(){ // int N,qu; // cin>>N>>qu; // int A[N],B[N],D[N]; // for(int q=0;q<N-1;q++){ // cin>>A[q]>>B[q]>>D[q]; // } // Init(N,A,B,D); // for(int q=0;q<N;q++){ // cout<<vis[q]<<" "; // } // cout<<endl; // while(qu--){ // int S,T; // cin>>S>>T; // int X[S],Y[T]; // for(int q=0;q<S;q++)cin>>X[q]; // for(int q=0;q<T;q++)cin>>Y[q]; // cout<<Query(S,X,T,Y)<<endl; // } // }