#include "factories.h"
#include <bits/stdc++.h>
#define FOR(i, x, n) for(int i = x; i < n; i++)
#define F0R(i, n) FOR(i, 0, n)
#define ROF(i, x, n) for(int i = n - 1; i >= x; i--)
#define R0F(i, n) ROF(i, 0, n)
#define WTF cout << "WTF" << endl
#define IOS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define F first
#define S second
#define PB push_back
#define ALL(x) x.begin(), x.end()
#define RALL(x) x.rbegin(), x.rend()
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
typedef vector<int> VI;
typedef vector<LL> VLL;
typedef vector<PII> VPII;
typedef vector<PLL> VPLL;
const int N = 1e5 + 7;
const LL INF = 1e18;
const int LOG = 20;
int n;
int par[N], sz[N];
int up[N][LOG], height[N];
bool vis[N];
LL dtr[N], opt[N];
VPII adj[N];
int getSz(int now, int p = -1) {
sz[now] = 1;
for(const auto &[on, v] : adj[now]) if (on != p && !vis[on]) sz[now] += getSz(on, now);
return sz[now];
}
int getCent(int now, int p, int nn) {
for(const auto &[on, v] : adj[now])
if (on != p && !vis[on] && sz[on] > nn / 2)
return getCent(on, now, nn);
return now;
}
void decomp(int now, int p = -1) {
getSz(now);
int c = getCent(now, -1, sz[now]);
//cout << "centroid is " << c << endl;
par[c] = p;
vis[c] = 1;
for(auto [on, w] : adj[c]) if (!vis[on]) decomp(on, c);
return;
}
void dfs(int now, int p = -1, int h = 0, LL dist = 0) {
up[now][0] = p;
height[now] = h;
dtr[now] = dist;
for(auto [on, w] : adj[now]) if (on != p) dfs(on, now, h + 1, dist + w);
return;
}
void Init(int nn, int A[], int B[], int D[]) {
n = nn;
F0R(i, n - 1) {
adj[ A[i] ].PB({B[i], D[i]});
adj[ B[i] ].PB({A[i], D[i]});
}
decomp(0);
dfs(0);
up[n][0] = n;
FOR(k, 1, LOG) F0R(i, n + 1)
up[i][k] = up[ up[i][k - 1] ][k - 1];
//F0R(i, n) cout << par[i] << ' '; cout << endl;
fill(opt, opt + n, INF);
return;
}
int lca(int a, int b) {
if (height[a] < height[b]) swap(a, b);
R0F(i, LOG) if (height[a] - (1 << i) >= height[b]) a = up[a][i];
if (a == b) return a;
R0F(i, LOG) if (up[a][i] != up[b][i])
a = up[a][i], b = up[b][i];
return up[a][0];
}
LL dist(int a, int b) {
int z = lca(a, b);
return dtr[a] + dtr[b] - 2LL * dtr[z];
}
void add(int v) {
int now = v;
while(now != -1) {
opt[now] = min(opt[now], dist(now, v));
now = par[now];
}
return;
}
LL getMin(int v) {
LL ret = INF;
int now = v;
while(now != -1) {
ret = min(ret, opt[now] + dist(v, now));
now = par[now];
}
return ret;
}
void rem(int v) {
while(v != -1) {
opt[v] = INF;
v = par[v];
}
}
LL Query(int s, int xs[], int t, int ys[]) {
F0R(i, s) add(xs[i]);
LL ans = INF;
F0R(i, t) ans = min(ans, getMin(ys[i]));
F0R(i, s) rem(xs[i]);
return ans;
}
