#include "factories.h"
#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define pii pair <int , int>
#define arr3 array <int , 3>
using namespace std;
const int INF = 1e18;
const int maxn = 1e6 + 7;
bool del[maxn];
int n, dep[maxn], pos[maxn], log_2[maxn], parent[maxn], child[maxn], dp[maxn];
vector <pii> g[maxn];
vector <int> node = {-1};
pii mindep[20][maxn];
void dfs(int u, int p)
{
node.push_back(u);
for(pii e: g[u])
{
int v = e.fi, w = e.se;
if(v == p) continue;
dep[v] = dep[u] + w;
dfs(v, u);
node.push_back(u);
}
}
int LCA(int u, int v)
{
int l = pos[u], r = pos[v];
if(l > r) swap(l, r);
int k = log_2[r - l + 1];
pii ss = min(mindep[k][l], mindep[k][r-(1 << k)+1]);
return ss.se;
}
int dist(int u, int v)
{
return dep[u] + dep[v] - 2*dep[LCA(u, v)];
}
void count_child(int u, int p)
{
child[u] = 1;
for(pii e: g[u])
{
int v = e.fi;
if(v == p || del[v]) continue;
count_child(v, u);
child[u] += child[v];
}
}
int centroid(int u, int p, int sz)
{
for(pii e: g[u])
{
int v = e.fi;
if(v == p || del[v]) continue;
if(child[v] > sz/2) return centroid(v, u, sz);
}
return u;
}
void decompose(int u, int last)
{
count_child(u, u);
int root = centroid(u, u, child[u]);
del[root] = 1;
parent[root] = last;
for(pii e: g[root])
{
int v = e.fi;
if(!del[v]) decompose(v, root);
}
}
void build()
{
dfs(1, 0);
for(int i = 1; i <= 2*n - 1; i++)
{
if(i > 1) log_2[i] = log_2[i/2] + 1;
mindep[0][i] = {dep[node[i]], node[i]};
pos[node[i]] = i;
}
for(int j = 1; j < 20; j++)
{
for(int i = 1; i + (1 << j) - 1 <= 2*n - 1; i++)
{
mindep[j][i] = min(mindep[j-1][i], mindep[j-1][i + (1 << (j-1))]);
}
}
decompose(1, 0);
for(int i = 1; i <= n; i++) dp[i] = INF;
}
void Init(signed N, signed A[], signed B[], signed D[])
{
n = N;
for(int i = 0; i < n-1; i++)
{
int u = A[i], v = B[i], w = D[i];
u++, v++;
g[u].push_back({v, w});
g[v].push_back({u, w});
}
build();
}
void UPDATE(int u)
{
int p = u;
while(p != 0)
{
dp[p] = min(dp[p], dist(u, p));
p = parent[p];
}
}
void REMOVE(int u)
{
while(u != 0)
{
dp[u] = INF;
u = parent[u];
}
}
int ASK(int u)
{
int ans = INF, p = u;
while(p != 0)
{
ans = min(ans, dp[p] + dist(u, p));
p = parent[p];
}
return ans;
}
long long Query(signed S, signed X[], signed T, signed Y[])
{
int ans = INF;
for(int i = 0; i < S; i++) UPDATE(X[i]+1);
for(int i = 0; i < T; i++) ans = min(ans, ASK(Y[i]+1));
for(int i = 0; i < S; i++) REMOVE(X[i]+1);
return ans;
}
