#include "factories.h" #include "bits/stdc++.h" using namespace std; const long long MAXN=500000,inf=10000000000000000LL; int pod[MAXN]; long long nearest[MAXN]; bool used[MAXN]; vector<pair<int,long long>> anc[MAXN]; vector<pair<int,int>> edg[MAXN]; inline long long min1(long long a,long long b) { if(a>b)return b; return a; } int getSubSize(int start,int f) { pod[start]=1; for(auto i:edg[start]) { if(used[i.first]||f==i.first)continue; pod[start]+=getSubSize(i.first,start); } return pod[start]; } int findCentr(int start,int f,int sz) { for(auto i:edg[start]) { if(used[i.first]||f==i.first)continue; if(pod[i.first]>sz/2)return findCentr(i.first,start,sz); } return start; } void findDist(int start,int f,int dist,int centrAnc) { anc[start].push_back({centrAnc,dist}); for(auto i:edg[start]) { if(used[i.first]||f==i.first)continue; findDist(i.first,start,dist+i.second,centrAnc); } } void centrDec(int start) { int centr=findCentr(start,-1,getSubSize(start,-1)); used[centr]=1; anc[centr].push_back({centr,0}); for(auto i:edg[centr]) { if(used[i.first])continue; findDist(i.first,-1,i.second,centr); } for(auto i:edg[centr]) { if(used[i.first])continue; centrDec(i.first); } } void addNode(int n) { for(auto i:anc[n]) { nearest[i.first]=min1(nearest[i.first],i.second); } } long long query(int n) { long long ans=inf; for(auto i:anc[n]) { ans=min1(nearest[i.first]+i.second,ans); } return ans; } void Init(int N, int A[], int B[], int D[]) { for(int i=0;i<N-1;i++) { edg[A[i]].push_back({B[i],D[i]}); edg[B[i]].push_back({A[i],D[i]}); } centrDec(0); for(int i=0;i<N;i++) { nearest[i]=inf; } } long long Query(int S, int X[], int T, int Y[]) { long long ans=inf; for(int i=0;i<S;i++) { addNode(X[i]); } for(int i=0;i<T;i++) { ans=min1(ans,query(Y[i])); } for(int i=0;i<S;i++) { for(auto j:anc[X[i]]) { nearest[j.first]=inf; } } return ans; }