#include <bits/stdc++.h> #include "factories.h" using namespace std; #define show(n) cout<<n<<'\n' #define all(v) v.begin(), v.end() #define br cout<<"\n" #define pb push_back const int mxN = 5e5 + 10; const long long inf = 1e18; set<pair<int, int>> adj[mxN]; int out[mxN],sz[mxN],par[mxN],depth[mxN],parent[mxN]; long long sum[mxN], ans[mxN]; vector<vector<int>> dp; vector<int> euler,lg; struct fst_lca{ void dfs(int u,int p){ sz[u]=1; out[u]=(int)euler.size(); euler.pb(u); for(auto [v, w]:adj[u]){ if(v^p){ depth[v]=depth[u]+1; sum[v] = (long long) sum[u] + w; dfs(v,u); sz[u]+=sz[v]; out[u]=(int)euler.size(); euler.pb(u); } } } void init_dp(){ int csz=euler.size(); lg.resize(csz+1); for(int i=2;i<=csz;++i) lg[i]=lg[i>>1]+1; dp=vector<vector<int>>(csz,vector<int>(lg[csz]+1)); for(int i=0;i<csz;i++) dp[i][0]=euler[i]; for(int j=1;j<=lg[csz];j++){ for(int i=0;i+(1<<(j-1))<csz;i++){ dp[i][j]=comp(dp[i][j-1],dp[i+(1<<(j-1))][j-1]); } } } int comp(int u,int v) { return depth[u]<depth[v]?u:v; } int lca(int l,int r) { return comp(dp[l][lg[r-l+1]],dp[r-(1<<lg[r-l+1])+1][lg[r-l+1]]); } long long dist(int u,int v){ if(out[u]>out[v]) swap(u,v); return sum[u]+sum[v]-(sum[lca(out[u],out[v])]<<1); } } fst; struct centroid{ void pre_sz(int u,int p){ sz[u]=1; for(auto [v, w]:adj[u]){ if(v^p){ pre_sz(v,u); sz[u]+=sz[v]; } } } int find_cen(int u,int p,int r){ int mx=0,mxv; for(auto [v, w]:adj[u]){ if(v^p&&sz[v]>mx){ mxv=v,mx=sz[v]; } } if(mx<=sz[r]>>1) return u; return find_cen(mxv,u,r); } void decompose(int u=1,int p=-1){ pre_sz(u,-1); int cent=find_cen(u,-1,u); par[cent]=p; for(auto [it, w]:adj[cent]){ adj[it].erase({cent, w}); decompose(it,cent); } adj[cent].clear(); } void update(int u){ int c=u; while(c!=-1){ ans[c]=min(ans[c],fst.dist(u,c)); c=par[c]; } } void undo(int u){ int c=u; while(c!=-1){ ans[c] = inf; c=par[c]; } } long long qry(int u){ int c=u; long long res = inf; while(c!=-1){ res=min(res,ans[c]+fst.dist(u,c)); c=par[c]; } return res; } } cent; void Init(int N, int A[], int B[], int D[]) { for(int i = 0; i < N; ++i) ans[i] = inf; for(int i = 0; i < N - 1; ++i){ adj[A[i]].insert({B[i], D[i]}); adj[B[i]].insert({A[i], D[i]}); } fst.dfs(0, -1); fst.init_dp(); cent.decompose(0, -1); } long long Query(int S, int X[], int T, int Y[]) { long long ans = inf; for(int i = 0; i < S; ++i){ cent.update(X[i]); } for(int i = 0; i < T; ++i){ ans = min(ans, cent.qry(Y[i])); } for(int i = 0; i < S; ++i){ cent.undo(X[i]); } return ans; }