#include "factories.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1e18;
const int MAXN = 5.1e5;
struct edge_t {
int c[2];
ll w;
int other(int a) {
assert(a == c[0] || a == c[1]);
return c[0] ^ c[1] ^ a;
}
} E[MAXN];
vector<int> adj[MAXN];
bool isDead[MAXN];
int par[MAXN];
vector<ll> dists[MAXN]; // distances to parents
int dfsSz(int cur, int prv) {
if (isDead[cur]) return 0;
int ans = 1;
for (int e : adj[cur]) {
int nxt = E[e].other(cur);
if (nxt == prv) continue;
ans += dfsSz(nxt, cur);
}
return ans;
}
int getCentroid(int cur, int prv, int sz) {
if (isDead[cur]) return -1;
int curSz = 1;
for (int e : adj[cur]) {
int nxt = E[e].other(cur);
if (nxt == prv) continue;
int ch = getCentroid(nxt, cur, sz);
if (ch >= 0) {
return ch;
} else {
curSz += -1-ch;
}
}
if (curSz * 2 >= sz) {
return cur;
} else {
return -1-curSz;
}
}
void genDists(int cur, int centroid, int prv, ll dist) {
if (isDead[cur]) return;
if (cur != centroid) {
par[cur] = centroid;
}
dists[cur].push_back(dist);
for (int e : adj[cur]) {
int nxt = E[e].other(cur);
if (nxt == prv) continue;
genDists(nxt, centroid, cur, dist + E[e].w);
}
}
void buildCentroid(int cur) {
int sz = dfsSz(cur, -1);
cur = getCentroid(cur, -1, sz);
genDists(cur, cur, -1, 0);
isDead[cur] = true;
for (int e : adj[cur]) {
int nxt = E[e].other(cur);
if (isDead[nxt]) continue;
buildCentroid(nxt);
}
}
ll minDist[MAXN];
void Init(int N, int A[], int B[], int D[]) {
for (int e = 0; e < N-1; e++) {
E[e] = {A[e], B[e], D[e]};
adj[A[e]].push_back(e);
adj[B[e]].push_back(e);
}
for (int i = 0; i < N; i++) {
par[i] = -1;
}
buildCentroid(0);
for (int i = 0; i < N; i++) {
minDist[i] = INF;
}
for (int i = 0; i < N; i++) assert(dists[i].size() <= 25);
}
void update(int v, bool add = true) {
for (int cur = v, i = int(dists[v].size())-1; cur != -1; cur = par[cur], i--) {
assert(i >= 0);
if (add) {
minDist[cur] = min(minDist[cur], dists[v][i]);
} else {
minDist[cur] = INF;
}
}
}
ll query(int v) {
ll ans = INF;
for (int cur = v, i = int(dists[v].size())-1; cur != -1; cur = par[cur], i--) {
assert(i >= 0);
ans = min(ans, minDist[cur] + dists[v][i]);
}
return ans;
}
long long Query(int S, int X[], int T, int Y[]) {
for (int i = 0; i < S; i++) {
update(X[i]);
}
ll ans = INF;
for (int i = 0; i < T; i++) {
ans = min(ans, query(Y[i]));
}
for (int i = 0; i < S; i++) {
update(X[i], false);
}
return ans;
}
