#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 #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 p[MAX_N]; vector<int>a[MAX_N]; int sz[MAX_N]; int vi[MAX_N]; int co=0; int dfs(int x,int y){ sz[x]=1; co++; for (int i:a[x]){ if (i==y or vi[i])continue; sz[x]+=dfs(i,x); } return sz[x]; } int cent(int x){ co=0; dfs(x,0); int p=0; while (sz[x]>co/2){ int y=x; for (int i:a[x]){ if (sz[i]>co/2 and i!=p and !vi[i]){ p=x; x=i; break; } } if (y==x)break; } vi[x]=1; return x; } void Init(int n,int A[], int B[], int D[]){ for (int i=0;i<n-1;i++){ int x=A[i],y=B[i]; x++; y++; a[x].push_back(y); a[y].push_back(x); d[{x,y}]=d[{y,x}]=D[i]; } vector<int>lb(n+1); queue<pair<int,int>>o; o.push({1,0}); while (o.size()){ auto h=o.front(); o.pop(); if (vi[h.fi])continue; h.fi=cent(h.fi); lb[h.fi]=h.se; for (int i:a[h.fi]){ if (vi[i])continue; o.push({i,h.se+1}); } } queue<int>q; for (int i=1;i<=n;i++){ if (lb[i]==0){ q.push(i); } } while (q.size()){ int x=q.front(); q.pop(); queue<int>o; o.push(x); vector<int>l; map<int,int>vi; vi[x]=1; while (o.size()){ int h=o.front(); o.pop(); for (int i:a[h]){ if (vi[i] or lb[i]<=lb[x])continue; d[{i,x}]=d[{x,i}]=d[{h,x}]+d[{i,h}]; vi[i]=1; o.push(i); if (lb[i]==lb[x]+1){ p[i]=x; l.push_back(i); } } } for (int i:l)q.push(i); } } ll Query(int S,int X[],int T,int Y[]){ map<int,ll>dx; map<int,ll>dy; for (int i=0;i<S;i++){ X[i]++; int x=X[i]; dx[x]=-1; while (p[x]!=0){ x=p[x]; if (dx[x]==0){ dx[x]=d[{x,X[i]}]; } else{ dx[x]=min(dx[x],d[{x,X[i]}]); } } } ll ans=1e18; for (int i=0;i<T;i++){ Y[i]++; int x=Y[i]; dy[x]=-1; if (dx[x]){ ans=min(ans,dx[x]+dy[x]+(dx[x]==-1)+(dy[x]==-1)); } while (p[x]!=0){ x=p[x]; if (dy[x]==0){ dy[x]=d[{x,Y[i]}]; } else{ dy[x]=min(dy[x],d[{x,Y[i]}]); } if (dx[x]){ ans=min(ans,dx[x]+dy[x]+(dx[x]==-1)+(dy[x]==-1)); } } } return ans; }