#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<int>> adj(maxn);
vector<vector<ll>> adjd(maxn);
//run a centroid decomposition
int subsize[maxn];
bool marked[maxn];
ll dr[19][maxn];
ll mycomp[19][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 (int i = 0; i < adj[u].size(); i++) {
int nx = adj[u][i];
if (nx == p || marked[nx]) continue;
curdist[nx] = curdist[u] + adjd[u][i];
dfs(nx, u, op);
subsize[u] += subsize[nx];
}
}
int getcentroid(int u, int csize) {
curdist[u] = 0LL;
dfs(u, -1);
int cur = u;
bool fin = false;
while (!fin) {
fin = true;
for (int nx : adj[cur]) {
if (marked[nx] || nx == cp[cur]) continue;
if (subsize[nx] > csize/2) {
fin = false;
cur = nx;
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 (int cur : adj[cen]) {
if (!marked[cur])
go(cur, subsize[cur], level+1);
}
}
void Init(int N, int A[], int B[], int D[]) {
for (int i = 0; i < 19; i++) {
fill(mycomp[i], mycomp[i]+maxn, -1);
}
n = N;
for (int i = 0; i < N-1; i++) {
adj[A[i]].push_back(B[i]);
adj[B[i]].push_back(A[i]);
adjd[A[i]].push_back(D[i]);
adjd[B[i]].push_back(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 < 19; 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 < 19; 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 < 19; j++) {
if (mycomp[j][val] == -1) break;
curmin[mycomp[j][val]] = inf;
}
}
return ans;
}
//COULD NOT SUBMIT AT TIME FIRST SOLVED
