#pragma GCC optimize("Ofast")
#include "factories.h"
#include<bits/stdc++.h>
using namespace std;
const int MaxN = 5e5 + 7;
const int Log = 20;
vector<int> g[MaxN];
vector<long long> c[MaxN];
int p[MaxN], in[MaxN], arr[MaxN], d[MaxN], n, sz, cn, gl;
long long be[MaxN][Log], opt[MaxN];
bool vc[MaxN];
int dfssz(int s, int f) {
int x = 1;
for (int i = 0; i < g[s].size(); i++) {
if (g[s][i] != f && !vc[g[s][i]]) {
x += dfssz(g[s][i], s);
}
}
return x;
}
int dfsc(int s, int f) {
int x = 1;
bool ce = true;
for (int i = 0; i < g[s].size(); i++) {
if (g[s][i] != f && !vc[g[s][i]]) {
int a = dfsc(g[s][i], s);
if (a > sz / 2) {
ce=false;
}
x += a;
}
if (sz - x > sz / 2) {
ce = false;
}
if (ce) {
cn = s;
}
return x;
}
void dfs(int s, int f, long long dist, int po) {
if (d[s] < d[po]) {
return;
}
be[s][d[s] - d[po]] = dist;
for (int i = 0; i < g[s].size(); i++) {
if (g[s][i] != f) {
dfs(g[s][i], s, dist + c[s][i], po);
}
}
}
void comp(int s, int f, int du) {
sz = dfssz(s, -1);
dfsc(s, -1);
p[cn] = f;
vc[cn] = true;
d[cn] = du;
int tmp = cn;
for (int i = 0; i < g[tmp].size(); i++) {
if (!vc[g[tmp][i]]) {
comp(g[tmp][i], tmp, du + 1);
}
}
}
void Init(int N, int A[], int B[], int D[]) {
n = N;
int root;
for (int i = 0; i < n - 1; i++) {
g[A[i]].push_back(B[i]);
g[B[i]].push_back(A[i]);
c[A[i]].push_back(D[i]);
c[B[i]].push_back(D[i]);
}
comp(0, -1, 0);
for (int i = 0; i < n; i++) {
dfs(i, -1, 0, i);
}
fill(opt, opt + MaxN, 1e18);
}
long long Query(int S, int X[], int T, int Y[]) {
int s = S, t = T;
long long sk = 1e18;
for (int i = 0; i < s; i++) {
int a = X[i];
cnt = 0;
while (a != -1) {
opt[a] = min(opt[a], be[X[i]][cnt]);
a = p[a];
cnt++;
}
}
for (int i = 0; i < t; i++) {
int a = Y[i];
cnt = 0;
while (a != -1) {
sk = min(sk, be[Y[i]][cnt] + opt[a]);
a = p[a];
cnt++;
}
}
for (int i = 0; i < s; i++) {
int a = X[i];
while (a != -1) {
opt[a] = 1e18;
a = p[a];
}
}
return sk;
}
