#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 5e5 + 10;
int st[maxn], LOG[2 * maxn], a[2 * maxn], sz[maxn], cpar[maxn], h[maxn], RMQ[22][2 * maxn];
int cnt = 0;
ll dis[maxn], dp[maxn];
bool mark[maxn];
vector<pair<int, int> > t[maxn];
int lca(int v, int u){
if (v == u)
return v;
if (st[v] > st[u])
swap(v, u);
int len = st[u] - st[v] + 1;
int lg = LOG[len];
int me = RMQ[lg][st[v]], oth = RMQ[lg][st[v] + (len - (1 << lg))];
if (h[me] < h[oth])
return me;
return oth;
}
ll distance(int v, int u){
return dis[v] + dis[u] - 2ll * dis[lca(v, u)];
}
int dfs_sz(int v, int p = -1){
sz[v] = 1;
for (auto edge : t[v]){
int u = edge.first;
if (u != p and mark[u] == false)
sz[v] += dfs_sz(u, v);
}
return sz[v];
}
void centroid_decomposition(int v, int centpar = -1){
int Max = dfs_sz(v), parent = -1;
while (true){
bool found = 0;
for (auto edge : t[v]){
int u = edge.first;
if (u != parent and mark[u] == false and sz[u] > Max / 2){
parent = v;
v = u;
found = 1;
break;
}
}
if (!found)
break;
}
cpar[v] = centpar;
mark[v] = true;
for (auto u : t[v])
if (mark[u.first] == false)
centroid_decomposition(u.first, v);
}
void dfs(int v, int par = -1){
st[v] = cnt;
a[cnt ++] = v;
for (auto edge : t[v]){
int u = edge.first, w = edge.second;
if (u != par){
h[u] = h[v] + 1;
dis[u] = dis[v] + w;
dfs(u, v);
a[cnt ++] = v;
}
}
}
void Init(int N, int A[], int B[], int D[]){
for (int i = 0; i < N - 1; i++){
int v = A[i], u = B[i], w = D[i];
t[v].push_back({u, w});
t[u].push_back({v, w});
}
dfs(0);
for (int i = 0; i < cnt; i++)
RMQ[0][i] = a[i];
for (int i = 1; i <= 20; i++){
for (int j = 0; j + (1 << i) <= cnt; j++){
int me = RMQ[i - 1][j], oth = RMQ[i - 1][j + (1 << (i-1))];
if (h[me] <= h[oth])
RMQ[i][j] = me;
else
RMQ[i][j] = oth;
}
}
LOG[1] = 0;
for (int i = 2; i <= cnt; i++)
LOG[i] = LOG[i / 2] + 1;
centroid_decomposition(0);
memset(dp, 63, sizeof dp);
}
long long Query(int S, int X[], int T, int Y[]){
for (int i = 0; i < S; i++){
int v = X[i];
while (v != -1){
dp[v] = min(dp[v], distance(v, X[i]));
v = cpar[v];
}
}
ll answer = 1e18;
for (int i = 0; i < T; i++){
int v = Y[i];
while (v != -1){
answer = min(answer, dp[v] + distance(v, Y[i]));
v = cpar[v];
}
}
for (int i = 0; i < S; i++){
int v = X[i];
while (v != -1){
dp[v] = 1e18;
v = cpar[v];
}
}
return answer;
}
