#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1e17;
int n;
vector<int> sz, nxt;
vector<vector<pair<int,int> > > g;
vector<vector<ll> > d;
vector<bool> block;
vector<ll> mn;
void init_dfs(int u, int par, ll curr_dist = 0) {
d[u].push_back(curr_dist);
sz[u] = 1;
for(auto p: g[u]) {
int v, w; tie(v, w) = p;
if(block[v] || v == par) continue;
init_dfs(v, u, curr_dist + w);
sz[u] += sz[v];
}
}
void calc(int src, int par) {
int cen = src;
while(true) {
bool found = false;
for(auto p: g[cen]) if(sz[p.first] < sz[cen] && sz[p.first] << 1 >= sz[src]) {
cen = p.first;
found = true;
break;
}
if(!found) break;
}
block[cen] = true;
nxt[cen] = par;
init_dfs(cen, -1);
// cout << cen << ' ' << nxt[cen] << endl;
for(auto p: g[cen]) if(!block[p.first]) calc(p.first, cen);
}
void Init(int N, int A[], int B[], int D[]) {
n = N;
g.resize(n), sz.resize(n), nxt.resize(n), d.resize(n), block.resize(n);
mn.assign(n, INF);
for(int i = 0; i < n-1; i++) {
g[A[i]].emplace_back(B[i], D[i]);
g[B[i]].emplace_back(A[i], D[i]);
}
init_dfs(0, -1);
calc(0, -1);
}
ll Query(int S, int X[], int T, int Y[]) {
ll ret = INF;
for(int i = 0; i < S; i++) for(int j = d[X[i]].size()-1, v = X[i]; j > 0; j--, v = nxt[v])
mn[v] = min(d[X[i]][j], mn[v]);
for(int i = 0; i < T; i++) for(int j = d[Y[i]].size()-1, v = Y[i]; j > 0; j--, v = nxt[v])
ret = min(mn[v] + d[Y[i]][j], ret);
for(int i = 0; i < S; i++) for(int j = d[X[i]].size()-1, v = X[i]; j > 0; j--, v = nxt[v])
mn[v] = INF;
return ret;
}
