#include "factories.h"
#include<bits/stdc++.h>
using namespace std;
int nr, rmq[20][1000009], lg[1000009], lev[500009], firstPos[500009], lastPos[500009], color[500009], ap[500009];
long long depth[500009], ans;
const long long INF = 1LL << 59;
vector < pair < int, int > > v[500009];
void dfs (int nod, int tata)
{
rmq[0][++nr] = nod, firstPos[nod] = nr;
for (auto it : v[nod])
if (it.first != tata)
depth[it.first] = depth[nod] + it.second,
lev[it.first] = lev[nod] + 1, dfs (it.first, nod),
rmq[0][++nr] = nod;
lastPos[nod] = nr;
}
int getHigher (int x, int y)
{
if (lev[x] > lev[y]) return y;
return x;
}
int getLCA (int x, int y)
{
x = firstPos[x], y = firstPos[y];
if (x > y) swap (x, y);
int p = lg[y - x + 1];
return getHigher (rmq[p][x], rmq[p][y - (1 << p) + 1]);
}
bool cmp (int x, int y)
{
return (firstPos[x] < firstPos[y]);
}
void Init (int N, int A[], int B[], int D[])
{
for (int i=0; i<N - 1; i++)
{
A[i] ++, B[i] ++;
v[A[i]].push_back ({B[i], D[i]});
v[B[i]].push_back ({A[i], D[i]});
}
dfs (1, -1);
for (int i=2; i<=nr; i++)
{
lg[i] = lg[i - 1];
if ((2 << lg[i]) <= i)
lg[i] ++;
}
for (int i=1; i<=lg[nr]; i++)
for (int j=1; j + (1 << i) - 1<=nr; j++)
rmq[i][j] = getHigher (rmq[i - 1][j], rmq[i - 1][j + (1 << (i - 1))]);
}
bool isAncestor (int up, int down)
{
return (firstPos[up] <= firstPos[down] && lastPos[down] <= lastPos[up]);
}
vector < int > sons[500009];
pair < long long, long long > solve (int nod)
{
pair < long long, long long > curr = {INF, INF};
if (color[nod] == 1) curr.first = depth[nod];
else
if (color[nod] == 2) curr.second = depth[nod];
for (auto it : sons[nod])
{
auto currIt = solve (it);
if (currIt.first < curr.first) curr.first = currIt.first;
if (currIt.second < curr.second) curr.second = currIt.second;
}
if (curr.first + curr.second - 2LL * depth[nod] < ans)
ans = curr.first + curr.second - 2LL * depth[nod];
return curr;
}
int stk[500009], h[500009];
long long Query (int S, int X[], int T, int Y[])
{
nr = 0, ans = INF;
for (int i=0; i<S; i++)
X[i] ++, h[++nr] = X[i], color[X[i]] = 1, ap[X[i]] = 1;
for (int i=0; i<T; i++)
Y[i] ++, h[++nr] = Y[i], color[Y[i]] = 2, ap[Y[i]] = 1;
sort (h + 1, h + nr + 1, cmp);
for (int i=nr - 1; i>=1; i--)
{
int curr = getLCA (h[i], h[i + 1]);
if (ap[curr] == 0)
ap[curr] = 2, h[++nr] = curr;
}
sort (h + 1, h + nr + 1, cmp);
int l = 0, root = 0;
for (int i=1; i<=nr; i++)
{
while (l > 0 && isAncestor (stk[l], h[i]) == 0) l --;
if (l == 0) root = h[i];
else sons[stk[l]].push_back (h[i]);
stk[++l] = h[i];
}
solve (root);
for (int i=1; i<=nr; i++)
ap[h[i]] = 0, color[h[i]] = 0,
sons[h[i]].clear ();
return ans;
}
