#include <bits/stdc++.h>
#include "factories.h"
using namespace std;
typedef long long ll;
const int maxn = 5e5 + 10;
const ll inf = 1e18;
vector < pair < int, ll > > g[maxn];
int n, root, sub[maxn], used[maxn], par[maxn];
int f[2 * maxn], in[maxn], timer;
ll depth[maxn];
void calc(int v, int p, bool st)
{
if (st)
{
f[++ timer] = v;
in[v] = timer;
}
sub[v] = 1;
for (pair < int, ll > nb : g[v])
{
int u = nb.first;
if (u == p)
continue;
if (st)
depth[u] = depth[v] + nb.second;
calc(u, v, st);
sub[v] += sub[u];
if (st)
f[++ timer] = v;
}
}
const int maxlog = 21;
ll dp[maxn * 2][maxlog], lg[maxn * 2];
void build_sparse_table()
{
/**for (int i = 1; i <= timer; i ++)
cout << f[i] << " ";
cout << endl;*/
for (int i = 1; i <= timer; i ++)
dp[i][0] = depth[f[i]], lg[i] = lg[i / 2] + 1;
for (int j = 1; j < lg[timer]; j ++)
for (int i = 1; i <= timer - (1 << j) + 1; i ++)
{
dp[i][j] = dp[i][j - 1];
if (dp[i + (1 << (j - 1))][j - 1] < dp[i][j])
dp[i][j] = dp[i + (1 << (j - 1))][j - 1];
}
}
ll dist(int v, int u)
{
int l = in[v], r = in[u];
if (l > r)
swap(l, r);
int len = lg[r - l + 1] - 1;
return depth[v] + depth[u] - 2 * min(dp[l][len], dp[r - (1 << len) + 1][len]);
}
int decompose(int v, int p, int sz)
{
for (pair < int, ll > nb : g[v])
{
int u = nb.first;
if (u == p || used[u])
continue;
if (sub[u] > sz / 2)
return decompose(u, v, sz);
}
/// v is centroid
used[v] = 1;
for (pair < int, ll > nb : g[v])
{
int u = nb.first;
if (used[u])
continue;
if (u == p)
calc(u, v, 0);
par[decompose(u, v, sub[u])] = v;
}
return v;
}
void Init(int N, int A[], int B[], int D[])
{
n = N;
for (int i = 0; i < n - 1; i ++)
{
g[A[i]].push_back({B[i], (ll)D[i]});
g[B[i]].push_back({A[i], (ll)D[i]});
}
calc(0, -1, 1);
decompose(0, -1, n);
build_sparse_table();
///cout << dist(2, 5) << endl;
}
ll Query(int S, int X[], int T, int Y[])
{
ll ans = inf;
for (int i = 0; i < S; i ++)
for (int j = 0; j < T; j ++)
if (dist(X[i], Y[j]) < ans)
ans = dist(X[i], Y[j]);
return ans;
}
