//by yjz
#include "factories.h"
#include<bits/stdc++.h>
#define FF first
#define SS second
#define MP make_pair
#define PB push_back
typedef long long ll;
using namespace std;
const int maxn = 500111;
int n;
vector<pair<int,int> > con[maxn];
int fa[20][maxn];
ll len[maxn];
int dfn[maxn], dtot;
vector<pair<int,ll> > ncon[maxn];
int type[maxn];
void dfs(int x)
{
for (int i=1; i<20; i++) fa[i][x] = fa[i-1][fa[i-1][x]];
dfn[x] = ++dtot;
for (auto e : con[x])
{
int u = e.FF;
if (u==fa[0][x]) continue;
fa[0][u] = x;
len[u] = len[x]+e.SS;
dfs(u);
}
}
int get_lca(int x, int y)
{
if (len[x]>len[y]) swap(x, y);
for (int i=19; i>=0; i--) if (fa[i][y]&&len[fa[i][y]]>=len[x]) y = fa[i][y];
if (x==y) return x;
for (int i=19; i>=0; i--) if (fa[i][x]!=fa[i][y])
{
x = fa[i][x];
y = fa[i][y];
}
return fa[0][x];
}
void Init(int N, int A[], int B[], int D[])
{
for (int i=0; i<maxn; i++) type[i] = 2;
n = N;
for (int i=0; i<n-1; i++)
{
int x = A[i], y = B[i], c = D[i];
x++; y++;
con[x].PB(MP(y, c));
con[y].PB(MP(x, c));
}
len[1] = 0;
dfs(1);
}
bool cmp(pair<int,bool> X, pair<int,bool> Y) {return dfn[X.FF]<dfn[Y.FF];}
const ll inf = 4e18;
void upd(ll &x, ll v) {x=min(x, v);}
void add_edge(int x, int p) {ncon[p].PB(MP(x, len[x]-len[p]));}// cerr<<"add_edge:"<<p<<"->"<<x<<" "<<len[x]-len[p]<<endl;}
ll ans;
pair<ll,ll> calc_ans(int x)
{
pair<ll,ll> ret = MP(inf, inf);
if (type[x]==0) ret.FF = 0;
if (type[x]==1) ret.SS = 0;
for (auto e : ncon[x])
{
pair<ll,ll> pp = calc_ans(e.FF);
upd(ret.FF, pp.FF+e.SS);
upd(ret.SS, pp.SS+e.SS);
}
upd(ans, ret.FF+ret.SS);
return ret;
}
long long Query(int S, int X[], int T, int Y[])
{
// cerr<<"Query:"<<endl;
vector<pair<int,bool> > v;
for (int i=0; i<S; i++) v.PB(MP(X[i]+1, 0)), type[X[i]+1] = 0;
for (int i=0; i<T; i++) v.PB(MP(Y[i]+1, 1)), type[Y[i]+1] = 1;
sort(v.begin(), v.end(), cmp);
vector<int> st, all;
st.PB(v[0].FF); all.PB(v[0].FF);
for (int i=1; i<v.size(); i++)
{
int x = v[i].FF;
int p = get_lca(x, st.back());
// cerr<<"x="<<x<<" last="<<st.back()<<" p="<<p<<endl;
while (st.size()>2&&len[st[st.size()-2]]>=len[p])
{
add_edge(st.back(), st[st.size()-2]);
st.pop_back();
}
if (st.size()>0&&st.back()!=p) //add_edge p->left_most
{
add_edge(st.back(), p);
st.pop_back();
}
if (st.size()==0||st.back()!=p) st.PB(p), all.PB(p);
if (x!=p) st.PB(x), all.PB(x);
}
ans = inf;
assert(st.size()>0);
while (st.size()>1) add_edge(st.back(), st[st.size()-2]), st.pop_back();
calc_ans(st[0]);
for (auto t : all) ncon[t].clear(), type[t] = 2;
return ans;
}
