#include<bits/stdc++.h>
#include "factories.h"
using namespace std;
const int maxn = 5e5;
int n, q, h[maxn], x[1000000], y[1000000], child[maxn], par[maxn], st[maxn][20];
bool del[maxn];
long long ans[maxn], dis[maxn];
vector<pair<int, long long>> adj[maxn + 1];
void DFS(int u, int p){
child[u] = 1;
for (auto [v, w] : adj[u]) if (v != p && !del[v]){
DFS(v, u);
child[u] += child[v];
}
return;
}
int find_centroid(int u, int p, int num){
for (auto [v, w] : adj[u]) if (v != p && !del[v]){
if (child[v] > num / 2) return find_centroid(v, u, num);
}
return u;
}
void BFS(int u){
queue<int> q;
q.push(u);
while(!q.empty()){
int cur = q.front();
q.pop();
for (auto [v, w] : adj[cur]) if (!del[v] && par[v] != u){
par[v] = u;
q.push(v);
}
}
return;
}
void compute(int u){
DFS(u, -1);
int centroid = find_centroid(u, -1, child[u]);
// cout << centroid << '\n';
del[centroid] = true;
BFS(centroid);
for (auto [v, w] : adj[centroid]) if (!del[v])
compute(v);
return;
}
void DFS1(int u, int p){
for (auto [v, w] : adj[u]) if (v != p){
h[v] = h[u] + 1;
dis[v] = dis[u] + w;
st[v][0] = u;
for (int i = 1; (1 << i) <= h[v] ; ++i){
st[v][i] = st[st[v][i - 1]][i - 1];
}
DFS1(v, u);
}
return;
}
int lca(int u, int v){
if (h[u] > h[v]) swap(u, v);
int k = h[v] - h[u];
for (int i = 0; i <= 19; ++i) if (k & (1 << i))
v = st[v][i];
if (u == v) return u;
for (int i = 19; i >= 0; --i) if (st[u][i] != st[v][i]){
u = st[u][i];
v = st[v][i];
}
return st[u][0];
}
long long length(int u, int v){
return dis[u] + dis[v] - 2 * dis[lca(u, v)];
}
void Init(int N, int A[], int B[], int D[]){
n = N;
memset(del, false, sizeof(del));
fill(par, par + maxn, -1);
for (int i = 0; i < n; ++i){
ans[i] = 1e18;
}
for (int i = 0; i < n - 1; ++i){
adj[A[i]].push_back({B[i], D[i]});
adj[A[i]].push_back({B[i], D[i]});
}
compute(0);
// for (int i = 0; i < n; ++i) cout << par[i] << ' ';
// cout << '\n';
DFS1(0, -1);
return;
}
long long Query(int S, int X[], int T, int Y[]){
long long res = 1e18;
for (int i = 0; i < T; ++i){
int p = Y[i];
while(p != -1){
ans[p] = min(ans[p], length(Y[i], p));
p = par[p];
}
};
for (int i = 0; i < S; ++i){
int p = X[i];
while(p != -1){
res = min(res, ans[p] + length(X[i], p));
p = par[p];
}
}
for (int i = 0; i < T; ++i){
int p = Y[i];
while(p != -1){
ans[p] = 1e18;
p = par[p];
}
};
return res;
}
