/*
* Written by
* ______ _ _ ______ ____ ____ ____ ____
* |_ _|| |_| ||_ _||_ || __ || __ |/ _/
* | | | _ | | | / / || |||| ||| |__
* | | | | | | | | | |_ ||__||||__||\__ \
* |__| |_| |_| |__| |___||____||____|/____/
*/
//#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
#define nmax 500500
#define ll long long
#define ii pair<int, int>
const ll inf = (ll)1e15;
int n, sz[nmax], p[nmax], r[nmax], depth[nmax], rmq[nmax<<1][22], ln[nmax<<2], pos[nmax], euler[nmax<<2], ea;
ll ans[nmax], sum[nmax];
vector<ii> adj[nmax];
int dfs(int u, int p = -1)
{
sz[u] = 1;
for(auto [C, v]: adj[u]) {
if(v != p && !r[v]) sz[u] += dfs(v, u);
}
return sz[u];
}
int find_centroid(int m, int u, int p = -1)
{
for(auto [C, v]: adj[u]) {
if(v != p && !r[v] && 2 * sz[v] > m)
return find_centroid(m, v, u);
}
return u;
}
int centroid(int u = 0)
{
u = find_centroid(dfs(u), u);
r[u] = 1;
p[u] = -1;
for(auto [C, v]: adj[u]) {
if(!r[v]) p[centroid(v)] = u;
}
return u;
}
void dfs2(int u, int p = -1)
{
pos[u] = ea;
euler[ea++] = u;
for(auto [C, v]: adj[u]) {
if(v == p) continue;
depth[v] = depth[u] + 1;
sum[v] = sum[u] + C;
dfs2(v, u);
euler[ea++] = u;
}
}
int lca(int x, int y)
{
x = pos[x];
y = pos[y];
if(x > y) swap(x, y);
int j = ln[y - x + 1];
return depth[euler[rmq[x][j]]] < depth[euler[rmq[y - (1 << j) + 1][j]]] ? euler[rmq[x][j]] : euler[rmq[y - (1 << j) + 1][j]];
}
inline ll dist(int x, int y)
{
return sum[x] + sum[y] - 2 * sum[lca(x, y)];
}
void Init(int N, int A[], int B[], int D[])
{
n = N;
for(int i = 0; i < n - 1; ++i) {
adj[A[i]].push_back(ii(D[i], B[i]));
adj[B[i]].push_back(ii(D[i], A[i]));
}
centroid();
fill(ans, ans + n, inf);
sum[0] = depth[0] = 0;
dfs2(0);
ln[1] = 0;
for(int i = 2; i < ea + 1; ++i) {
ln[i] = ln[i >> 1] + 1;
}
for(int i = 0; i < ea; ++i)
rmq[i][0] = i;
for(int j = 1; j < 21; ++j) {
for(int i = 0; i + (1 << j) - 1 < ea; ++i) {
if(depth[euler[rmq[i][j - 1]]] < depth[euler[rmq[i + (1 << (j - 1))][j - 1]]])
rmq[i][j] = rmq[i][j - 1];
else
rmq[i][j] = rmq[i + (1 << (j - 1))][j - 1];
}
}
}
void update(int y, bool del)
{
for(int x = y; x != -1; x = p[x]) {
if(del) ans[x] = inf;
else ans[x] = min(ans[x], dist(x, y));
}
}
ll get(int y)
{
ll res = inf;
for(int x = y; x != -1; x = p[x])
res = min(res, ans[x] + dist(x, y));
return res;
}
ll Query(int S, int X[], int T, int Y[])
{
ll res = inf;
if(S <= 10 && T <= 10) {
for(int i = 0; i < S; ++i) {
for(int j = 0; j < T; ++j)
res = min(res, dist(X[i], Y[j]));
}
return res;
}
for(int i = 0; i < S; ++i) {
update(X[i], 0);
}
for(int i = 0; i < T; ++i) {
res = min(res, get(Y[i]));
}
for(int i = 0; i < S; ++i) {
update(X[i], 1);
}
return res;
}
