#include "factories.h" #include <bits/stdc++.h> using namespace std; const long long INF = 1e18; const int NMAX = 500500; vector<pair<int,int>> g[NMAX]; long long dp[NMAX], best[NMAX]; int tin[NMAX], tout[NMAX], sz[NMAX], par[NMAX], us[NMAX]; int up[21][NMAX]; int tim; long long ans; void dfs(int v,int p,long long sum){ tin[v]=tim++; dp[v]=sum; up[0][v]=p; for(int i=1;i<=20;i++) up[i][v]=up[i-1][up[i-1][v]]; for(auto [to,c]:g[v]){ if(to!=p) dfs(to,v,sum+c); } tout[v]=tim; } void precalc(int v,int p){ sz[v]=1; for(auto [to,_]:g[v]){ if(to!=p && !us[to]){ precalc(to,v); sz[v]+=sz[to]; } } } int get(int v,int p,int n){ for(auto [to,_]:g[v]){ if(sz[to]>n/2 && to!=p && !us[to]) return get(to,v,n); } return v; } bool check(int a,int b){ return tin[a]<=tin[b] && tout[b]<=tout[a]; } int lca(int a,int b){ if(check(a,b)) return a; if(check(b,a)) return b; for(int i=20;i>=0;i--){ if(!check(up[i][a],b)) a=up[i][a]; } return up[0][a]; } long long dist(int a,int b){ return dp[a]+dp[b]-2*dp[lca(a,b)]; } void build(int v,int p){ precalc(v,-1); int c=get(v,-1,sz[v]); us[c]=1; par[c]=p; for(auto k:g[c]){ if(!us[k.first]) build(k.first,c); } } void upd(int v,int x){ best[v]=min(best[v],dist(v,x)); if(par[v]<0) return; upd(par[v],x); } void nulify(int v){ best[v]=INF; if(par[v]<0) return; nulify(par[v]); } void res(int v,int x){ ans=min(ans,dist(v,x)+best[v]); if(par[v]<0) return; res(par[v],x); } // ============================ // Батч API // ============================ void Init(int N, int A[], int B[], int D[]) { tim = 0; for(int i=0;i<=N;i++){ g[i].clear(); dp[i]=0; best[i]=INF; tin[i]=tout[i]=0; par[i]=-1; us[i]=0; sz[i]=0; } for(int i=0;i<N-1;i++){ g[A[i]].push_back({B[i], D[i]}); g[B[i]].push_back({A[i], D[i]}); } dfs(0,0,0); build(0,-1); for(int i=0;i<N;i++) best[i]=INF; } long long Query(int S, int X[], int T, int Y[]) { for(int i=0;i<S;i++) upd(X[i], X[i]); ans = INF; for(int i=0;i<T;i++) res(Y[i], Y[i]); for(int i=0;i<S;i++) nulify(X[i]); return ans; }