#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 gl;
int dfs(int x,int y){
sz[x]=1;
co++;
for (int i:a[x]){
if (i==y or vi[i])continue;
d[{i,gl}]=d[{gl,i}]=d[{i,x}]+d[{x,gl}];
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;
gl=x;
dfs(x,0);
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;
lb[0]=-1;
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]=lb[h.se]+1;
p[h.fi]=h.se;
for (int i:a[h.fi]){
if (vi[i])continue;
o.push({i,h.fi});
}
}
queue<int>q;
for (int i=1;i<=n;i++){
if (lb[i]==0){
q.push(i);
}
}
// int cp=0;
// 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]){
// cp++;
// 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);
// }
// cout << cp << endl;
// cout << p[] << endl;
// cout << endl;
}
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;
}
