#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 5e5+10;
const ll INF = 1e18;
int n;
vector< pair<int,int> > g[N];
ll lev[N];
vector<int> eul, dep;
int rmq[N*2 + 100][20], val[N*2 + 100][20], first[N];
void lcadfs(int u, int f, ll l, int d) {
lev[u] = l;
first[u] = eul.size();
eul.push_back(u); dep.push_back(d);
for(auto it : g[u]) if(it.first != f) {
lcadfs(it.first, u, l + it.second, d + 1);
eul.push_back(u); dep.push_back(d);
}
}
int lca(int u, int v) {
int l = first[u], r = first[v];
if(r < l) swap(l,r);
int k = 31 - __builtin_clz(r-l+1);
int a = rmq[l][k];
int b = rmq[r - (1<<k) + 1][k];
return (dep[a] < dep[b] ? eul[a] : eul[b]);
}
ll dist(int u, int v) {
return lev[u] + lev[v] - 2ll*lev[lca(u,v)];
}
int Deleted[N], sub[N], head[N];
int subdfs(int u, int f) {
sub[u] = 1;
for(auto it : g[u]) if(it.first != f && !Deleted[it.first])
sub[u] += subdfs(it.first, u);
return sub[u];
}
int get_centroid(int u, int f, int lim) {
for(auto it : g[u]) if(it.first != f && !Deleted[it.first])
if(2 * sub[it.first] > lim) return get_centroid(it.first, u, lim);
return u;
}
void decompose(int s, int dad) {
subdfs(s,-1);
int u = get_centroid(s, -1, sub[s]);
head[u] = dad;
Deleted[u] = 1;
for(auto it : g[u]) if(!Deleted[it.first])
decompose(it.first, u);
}
ll mnDist[N]; int deNode[N];
void Init(int n_, int A[], int B[], int D[]) {
n = n_;
for(int i = 0; i < n-1; i++) {
g[A[i]].push_back({B[i], D[i]});
g[B[i]].push_back({A[i], D[i]});
}
lcadfs(0,-1,0,0);
int sz = eul.size();
for(int i = 0; i < sz; i++) rmq[i][0] = i;
for(int j = 1; j < 20; j++) {
for(int i = 0; i + (1<<j) - 1 < sz; i++) {
int a = rmq[i][j-1];
int b = rmq[i + (1<<(j-1))][j-1];
rmq[i][j] = (dep[a] < dep[b] ? a : b);
}
}
decompose(0,-1);
for(int i = 0; i < n; i++)
mnDist[i] = INF, deNode[i] = -1;
}
void add(int u) {
for(int p = u; p + 1; p = head[p]) {
ll d = dist(u, p);
if(d < mnDist[p]) mnDist[p] = d, deNode[p] = u;
}
}
void remove(int u) {
for(int p = u; p + 1; p = head[p])
mnDist[p] = INF, deNode[p] = -1;
}
ll get(int u) {
ll ret = INF;
for(int p = u; p + 1; p = head[p]) if(deNode[p] + 1)
ret = min(ret, dist(u, deNode[p]));
return ret;
}
ll Query(int S, int X[], int T, int Y[]) {
for(int i = 0; i < S; i++) add(X[i]);
ll ret = INF;
for(int i = 0; i < T; i++)
ret = min(ret, get(Y[i]));
for(int i = 0; i < S; i++) remove(X[i]);
return ret;
}
