#include "factories.h" #include <iostream> #include <cmath> #include <algorithm> #include <map> #include <unordered_map> #include <vector> #include <iomanip> #include <string> #include <queue> #include <set> #include <deque> #include <stdio.h> #include <stdlib.h> using namespace std; #define ll long long const ll inf=1e17; #define MAX_N 500000+5 #define MAX_Q 100000+5 #define MAX_SUM_ST 1000000+5 #define MAX_VALUE 1000000000+5 #define fi first #define se second static int N, Q; //map<pair<int,int>,ll>d; int par[MAX_N]; vector<pair<int,ll>>ma[MAX_N]; //vector<int> ma_[MAX_N]; int sz[MAX_N]; //int vi[MAX_N]; ll ans[MAX_N]; bool dead[MAX_N]; int cur_n=0; map<int,ll> dist[MAX_N]; //int gl; void dfs_init(int x,int p=0) { sz[x]=1; for(auto [y,w]:ma[x]) { if(y^p) dfs_init(y,x),sz[x]+=sz[y]; } } int find_centroid(int x) { for(auto [y,w]:ma[x]) { if(!dead[y] and sz[y]>(cur_n>>1)) { sz[x]-=sz[y]; sz[y]+=sz[x]; return find_centroid(y); } } return x; } int cur; void compute(int x,int p=0,ll d=0) { dist[x][cur]=d; for(auto [y,w]:ma[x]) { if(y!=p and !dead[y]) { compute(y,x,d+w); } } } void build(int x,int pr=0) { cur_n=sz[x]; int cen=find_centroid(x); par[cen]=pr; dead[cen]=1; cur=cen; compute(cen); for(auto [y,w]:ma[cen]) { if(!dead[y]) { build(y,cen); // ma_[cen].push_back(ch); } } // return cen; } int __p; void Init(int n,int A[], int B[], int D[]){ __p=n; for(int i=0;i<=n;i++){ ma[i].clear(); dead[i]=0; dist[i].clear(); } for (int i=0;i<n-1;i++){ int x=A[i],y=B[i]; x++; y++; ma[x].push_back({y,D[i]}); ma[y].push_back({x,D[i]}); // d[{x,y}]=d[{y,x}]=D[i]; } dfs_init(1); build(1); for(int i=1;i<=__p;i++)ans[i]=inf; } vector<int> chg; void change_color(ll x) { ll st=x; while(x>0) { chg.push_back(x); ans[x]=min(ans[x],dist[st][x]); x=par[x]; } } ll answer(ll x) { ll st=x; ll cur=inf; //cout<<"P "; while(x>0) { //cout<<x<<' '; cur=min(cur,ans[x]+dist[st][x]); x=par[x]; } //cout<<endl; return cur; } ll Query(int S,int X[],int T,int Y[]){ for(auto i:chg)ans[i]=inf; chg.clear(); // for(int i=1;i<=__p;i++)ans[i]=1e18; for(int i=0;i<S;i++) { change_color(X[i]+1); //cout<<X[i]+1<<' '; } //cout<<endl; ll fnl=inf; for(int i=0;i<T;i++) fnl=min(fnl,answer(Y[i]+1)); return fnl; }