#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pil pair<int, ll>
#define maxn 500010
int n;
vector<vector<pil>> adj(maxn);
//run a centroid decomposition
int subsize[maxn];
bool marked[maxn];
ll dr[18][maxn];
ll mycomp[18][maxn]; //which component i am in (specify by centroid is good)
ll curdist[maxn];
int cp[maxn];
ll inf = 1LL << 60;
ll curmin[maxn]; //for the queries
int cl;
int cc;
void dfs(int u, int p, bool op = false) {
cp[u] = p;
subsize[u] = 1;
if (op) {
// cout << u << " is in " << cc << " at level " << cl << endl;
dr[cl][u] = curdist[u];
mycomp[cl][u] = cc;
}
for (pil nx : adj[u]) {
if (nx.first == p || marked[nx.first]) continue;
curdist[nx.first] = curdist[u] + nx.second;
dfs(nx.first, u, op);
subsize[u] += subsize[nx.first];
}
}
inline int getcentroid(int u, int csize) {
curdist[u] = 0LL;
dfs(u, -1);
int cur = u;
bool fin = false;
while (!fin) {
fin = true;
for (pil nx : adj[cur]) {
if (marked[nx.first] || nx.first == cp[cur]) continue;
if (subsize[nx.first] > csize/2) {
fin = false;
cur = nx.first;
break;
}
}
}
return cur;
}
void go(int u, int csize, int level) {
int cen = getcentroid(u, csize);
curdist[cen] = 0LL;
cc = cen;
cl = level;
dfs(cen, -1, true);
marked[cen] = true;
for (pil cur : adj[cen]) {
if (!marked[cur.first])
go(cur.first, subsize[cur.first], level+1);
}
}
void Init(int N, int A[], int B[], int D[]) {
for (int i = 0; i < 18; i++) {
fill(mycomp[i], mycomp[i]+maxn, -1);
}
n = N;
for (int i = 0; i < N-1; i++) {
adj[A[i]].push_back(pil(B[i], D[i]));
adj[B[i]].push_back(pil(A[i], D[i]));
}
fill(curmin, curmin+maxn, inf);
go(0, n, 0);
}
ll Query(int S, int X[], int T, int Y[]) {
ll ans = inf;
for (int i = 0; i < S; i++) {
int val = X[i];
for (int j = 0; j < 18; j++) {
if (mycomp[j][val] == -1) break;
curmin[mycomp[j][val]] =
min(curmin[mycomp[j][val]], dr[j][val]);
}
}
for (int i = 0; i < T; i++) {
int val = Y[i];
for (int j = 0; j < 18; j++) {
if (mycomp[j][val] == -1) break;
ans = min(ans,
curmin[mycomp[j][val]] + dr[j][val]);
}
}
for (int i = 0; i < S; i++) {
int val = X[i];
for (int j = 0; j < 18; j++) {
if (mycomp[j][val] == -1) break;
curmin[mycomp[j][val]] = inf;
}
}
return ans;
}
//COULD NOT SUBMIT AT TIME FIRST SOLVED
