#include <bits/stdc++.h>
#include "factories.h"
#define LINF 0x3f3f3f3f3f3f3f3f
#define fi first
#define se second
#define el cout << '\n';
#define maxn int(5e5 + 5)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
int sz[maxn];
ll mn[maxn];
bool isc[maxn];
vector<pli> deps;
vector<pii> adj[maxn];
vector<pli> acs[maxn];
void dfscount(int u, int p = -1) {
sz[u] = 1;
for(pii x : adj[u]) {
int v = x.fi;
if(v != p && !isc[v]) {
dfscount(v, u);
sz[u] += sz[v];
}
}
}
int centroid(int u, int n, int p = -1) {
for(pii x : adj[u]) {
int v = x.fi;
if(v != p && !isc[v] && sz[v] > (n >> 1)) return centroid(v, n, u);
}
return u;
}
void dfs(int u, int p, ll d) {
deps.push_back({ d, u });
for(pii x : adj[u]) {
int v = x.fi, w = x.se;
if(v != p && !isc[v]) dfs(v, u, d + w);
}
}
void cd(int u, int p = -1) {
dfscount(u);
int c = centroid(u, sz[u]);
isc[c] = 1;
for(pii x : adj[c]) {
int v = x.fi, w = x.se;
if(!isc[v]) {
deps.clear();
dfs(v, c, w);
for(pli x : deps)
acs[x.se].push_back({ x.fi, c });
}
}
acs[c].push_back({ 0, c });
for(pii x : adj[c]) {
int v = x.fi;
if(!isc[v]) cd(v, c);
}
}
void Init(int N, int A[], int B[], int D[]) {
for(int i = 0; i < N - 1; i++) {
adj[A[i]].push_back({ B[i], D[i] });
adj[B[i]].push_back({ A[i], D[i] });
}
cd(0);
memset(mn, 0x3f, sizeof mn);
}
void paint(int u) {
for(pli x : acs[u]) {
ll d = x.fi;
int v = x.se;
mn[v] = min(mn[v], d);
}
}
void reset(int u) {
for(pli x : acs[u]) {
ll d = x.fi;
int v = x.se;
mn[v] = LINF;
}
}
ll get(int u) {
ll res = LINF;
for(pii x : acs[u]) {
ll d = x.fi;
int v = x.se;
res = min(res, mn[v] + d);
}
return res;
}
ll Query(int S, int X[], int T, int Y[]) {
ll res = LINF;
for(int i = 0; i < S; i++) paint(X[i]);
for(int i = 0; i < T; i++) res = min(res, get(Y[i]));
for(int i = 0; i < S; i++) reset(X[i]);
return res;
}
