#include "factories.h"
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
const long long maxn = 2e5 + 10;
vector < pair < long long, long long > > g[maxn];
long long n, sub[maxn], blocked[maxn];
long long all, half;
void calc(long long beg, long long from)
{
sub[beg] = 1;
for (auto &[nb, dist]: g[beg])
{
if(nb == from)continue;
if(blocked[nb])continue;
sub[beg] += sub[nb];
}
}
long long find_centroid(long long beg, long long from)
{
for (auto [nb, cost]: g[beg])
{
if(nb == from || blocked[nb])continue;
if(sub[nb] > half)return find_centroid(nb, beg);
}
return beg;
}
long long root, par[maxn];
long long decompose(long long v, long long from)
{
calc(v, -1);
all = sub[v];
half = all/2;
long long nc = find_centroid(v, -1);
par[nc] = from;
blocked[nc] = 1;
for (auto &[nb, w]: g[nc])
{
if(blocked[nb])continue;
int t = decompose(nb, nc);
}
return nc;
}
long long dep[maxn], p[maxn], pw[maxn];
long long a[maxn * 3], da[maxn * 3], tmr, label[maxn];
long long lg[maxn * 3], st[maxn * 3][20], dp[maxn * 3];
void dfs2(long long beg, long long from, long long d, long long up)
{
dep[beg] = d;
tmr ++;
a[tmr] = beg;
da[tmr] = d;
label[beg] = tmr;
dp[beg] = up;
for (auto &[nb, cost]: g[beg])
{
if(nb == from)continue;
pw[nb] = cost;
p[nb] = beg;
dfs2(nb, beg, d+1, up + cost);
tmr ++;
a[tmr] = beg;
da[tmr] = d;
}
}
long long lca(long long from, long long to)
{
long long l = label[from], r = label[to];
if(l > r)swap(l, r);
long long sz = r - l + 1;
long long lgche= lg[sz];
long long fh = st[l][lgche];
long long sh = st[r-(1 << lgche) + 1][lgche];
if(da[fh] < da[sh])return a[fh];
else return a[sh];
}
long long dist(long long u, long long v)
{
long long anc = lca(u, v);
return dp[u] + dp[v] - 2 * dp[anc];
}
long long best[maxn]; /// fix to ll
void Init(int N, int A[], int B[], int D[])
{
n = N;
for (long long i = 0; i < n-1; ++ i)
{
long long from = A[i], to = B[i], w = D[i];
from ++;
to ++;
g[from].pb({to, w});
g[to].pb({from, w});
}
root = decompose(1, -1);
for (long long i = 0; i <= n; ++ i)
best[i] = 1e17;
dfs2(1, 0, 0, 0);
long long step = 0, val = 1;
for (long long i = 0; i <= tmr; ++ i)
{
if(val * 2<= i)
{
step ++;
val *= 2;
}
lg[i] = step;
}
for (long long i = 1; i <= tmr; ++ i)
st[i][0] = i;
for (long long bit = 1; bit < 20; ++ bit)
{
for (long long i = 1; i + (1 << bit) - 1 <= tmr; ++ i)
{
long long fh = st[i][bit-1];
long long sh = st[i + (1 << (bit - 1))][bit-1];
if(da[fh] < da[sh])st[i][bit] = fh;
else st[i][bit] = sh;
}
}
}
long long Query(int S, int X[], int T, int Y[])
{
long long s, t;
s = S;
t = T;
/// update
for (long long i = 0; i < s; ++ i)
{
X[i] ++;
long long ver = X[i];
while(ver != par[root])
{
best[ver] = min(best[ver], dist(ver, X[i]));
ver = par[ver];
}
}
long long ans = 1e17;
for (long long i = 0; i < t; ++ i)
{
Y[i] ++;
long long ver = Y[i];
int cnt = 0;
while(ver != par[root])
{
cnt ++;
assert(cnt < n);
ans = min(ans, best[ver] + dist(ver, Y[i]));
ver = par[ver];
}
}
/// kak shte go mahna posle
for (long long i = 0; i < s; ++ i)
{
long long ver = X[i];
while(ver != par[root])
{
best[ver] = 1e17;
ver = par[ver];
}
}
return ans;
}
