#include<bits/stdc++.h> #include "factories.h" #define ll long long #define pll pair<ll,ll> using namespace std; vector<vector<pll>> e; vector<vector<pll>> anc; vector<ll> sz,dist; vector<bool> rem; ll getsz(ll u,ll p){ sz[u]=1; for(auto v:e[u]){ if(v.first==p or rem[v.first]) continue; sz[u]+=getsz(v.first,u); } return sz[u]; } ll getct(ll u,ll p,ll n){ for(auto v:e[u]){ if(v.first==p or rem[v.first]) continue; if(sz[v.first]>n/2) return getct(v.first,u,n); } return u; } void getdist(ll u,ll p,ll ct,ll d){ anc[u].push_back({ct,d}); for(auto v:e[u]){ if(v.first==p or rem[v.first]) continue; getdist(v.first,u,ct,d+v.second); } } void decompose(ll u){ getsz(u,u); ll ct=getct(u,u,sz[u]); rem[ct]=1; for(auto v:e[ct]){ if(rem[v.first]) continue; getdist(v.first,ct,ct,v.second); } for(auto v:e[ct]){ if(rem[v.first]) continue; decompose(v.first); } } void Init(int n, int A[], int B[], int D[]){ e.resize(n+1); rem.resize(n+1,0); sz.resize(n+1); dist.resize(n+1,1e18); anc.resize(n+1); for(ll i=0 ; i<n-1 ; i++){ e[A[i]].push_back({B[i],D[i]}); e[B[i]].push_back({A[i],D[i]}); } decompose(0); } long long Query(int S, int X[], int T, int Y[]){ ll i,ans=1e18; for(i=0 ; i<S ; i++){ for(auto v:anc[X[i]]){ dist[v.first]=1e18; } } for(i=0 ; i<T ; i++){ for(auto v:anc[Y[i]]){ dist[v.first]=1e18; } } for(i=0 ; i<S ; i++){ for(auto v:anc[X[i]]){ dist[v.first]=min(dist[v.first],v.second); } } for(i=0 ; i<S ; i++){ dist[X[i]]=0; } for(i=0 ; i<T ; i++){ for(auto v:anc[Y[i]]){ ans=min(ans,dist[v.first]+v.second); } } return ans; }