#include "factories.h"
#include<algorithm>
#define INF 999999999999999LL
using namespace std;
int Nxt[1000100], ed[1000100], L[1000100], P[500010];
int par[19][500010], num[500010], cnt, ran[500010], Dep[500010];
long long D[500010];
void DFS(int a, int pp){
num[a] = ++cnt;
int i;
for (i = P[a]; i; i = Nxt[i]){
if (pp != ed[i]){
par[0][cnt + 1] = num[a];
Dep[cnt + 1] = Dep[num[a]] + 1;
D[cnt + 1] = D[num[a]] + L[i];
DFS(ed[i], a);
}
}
ran[num[a]] = cnt;
}
int LCA(int a, int b){
if (Dep[a] < Dep[b])swap(a, b);
int d = Dep[a] - Dep[b], c = 0;
while (d){
if (d & 1){
a = par[c][a];
}
c++;
d >>= 1;
}
c = 19;
while (c--){
if (par[c][a] != par[c][b])a = par[c][a], b = par[c][b];
}
if (a != b)a = par[0][a];
return a;
}
void Init(int N, int A[], int B[], int D[]) {
int i, c = 0, j;
for (i = 0; i < N - 1; i++){
Nxt[++c] = P[A[i]]; ed[c] = B[i]; P[A[i]] = c; L[c] = D[i];
Nxt[++c] = P[B[i]]; ed[c] = A[i]; P[B[i]] = c; L[c] = D[i];
}
DFS(0, -1);
for (i = 0; i < 18; i++){
for (j = 1; j <= N; j++){
par[i + 1][j] = par[i][par[i][j]];
}
}
}
int w[1000010], pv, Col[500010];
long long Res, GS[500010], GT[500010];
void DFS2(int a){
long long S = INF, T = INF;
if (Col[a] == 1)S =0;
if (Col[a] == 2)T = 0;
Col[a] = 0;
int x;
while (pv != cnt && w[pv] <= ran[a]){
x = w[pv]; pv++;
DFS2(x);
S = min(S, GS[x] + D[x] - D[a]);
T = min(T, GT[x] + D[x] - D[a]);
}
Res = min(Res, S + T);
GS[a] = S, GT[a] = T;
}
long long Query(int S, int X[], int T, int Y[]) {
int i;
cnt = 0;
for (i = 0; i < S; i++)w[cnt++] = num[X[i]], Col[num[X[i]]] = 1;
for (i = 0; i < T; i++)w[cnt++] = num[Y[i]], Col[num[Y[i]]] = 2;
sort(w, w + cnt);
for (i = cnt - 1; i; i--){
w[cnt++] = LCA(w[i], w[i - 1]);
}
sort(w, w + cnt);
cnt = unique(w, w + cnt) - w;
Res = INF, pv = 0;
DFS2(1);
return Res;
}
