#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl "\n"
#define all(x) x.begin(), x.end()
vector<vector<pair<int, ll>>> graph;
vector<vector<int>> ctree;
int croot;
vector<vector<ll>> depth, subtree; // [level][v]
constexpr int L = 20;
int n;
vector<vector<int>> a, b;
vector<bool> vis;
vector<int> sz;
int calc(int v, int p, int l, int c) {
if (v == p and l >= 0)
depth[l][v] = 0;
if (l > 0)
subtree[l-1][v] = c;
sz[v] = 1;
for (auto [ne, w] : graph[v])
if (!vis[ne] and ne != p) {
if (l >= 0)
depth[l][ne] = depth[l][v]+w;
sz[v] += calc(ne, v, l, c);
}
return sz[v];
}
int centroid(int v, int l) {
int k = calc(v, v, -1, 0), c = v;
bool cont = true;
while (cont) {
cont = false;
for (auto [ne, w] : graph[c]) if (!vis[ne] and sz[ne] < sz[c] and 2*sz[ne] > k)
cont = true, c = ne;
}
calc(c, c, l, c);
vis[c] = true;
for (auto [ne, w] : graph[c]) {
if (!vis[ne])
ctree[c].push_back(centroid(ne, l+1));
}
return c;
}
void Init(int nn, int aa[], int bb[], int d[]) {
n = nn;
graph.resize(n);
ctree.resize(n);
a.resize(n);
b.resize(n);
vis.resize(n);
sz.resize(n);
depth.assign(L, vector<ll>(n));
subtree.assign(L, vector<ll>(n));
for (int i = 0; i < n-1; i++) {
graph[aa[i]].emplace_back(bb[i], d[i]);
graph[bb[i]].emplace_back(aa[i], d[i]);
}
croot = centroid(0, 0);
}
ll qq(int v, int l) {
if (a[v].empty() or b[v].empty()) {
a[v].clear(), b[v].clear();
return LLONG_MAX;
}
ll ax = LLONG_MAX, bx = LLONG_MAX;
vector<int> nxt;
for (int e : a[v]) {
ax = min(ax, depth[l][e]);
if (e != v)
a[subtree[l][e]].push_back(e), nxt.push_back(subtree[l][e]);
}
for (int e : b[v]) {
bx = min(bx, depth[l][e]);
if (e != v)
b[subtree[l][e]].push_back(e), nxt.push_back(subtree[l][e]);
}
/*cout << v << endl;
for (int e : a[v])
cout << " " << e;
cout << endl;
for (int e : b[v])
cout << " " << e;
cout << endl;*/
ll res = ax+bx;
for (int ne : nxt)
res = min(res, qq(ne, l+1));
a[v].clear(), b[v].clear();
return res;
}
long long Query(int s, int x[], int t, int y[]) {
for (int i = 0; i < s; i++)
a[croot].push_back(x[i]);
for (int i = 0; i < t; i++)
b[croot].push_back(y[i]);
return qq(croot, 0);
}
