//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 lv[maxn], fa[maxn], top[maxn], arr[maxn], sz[maxn], son[maxn];
ll len[maxn];
int dfn[maxn], dtot;
vector<pair<int,ll> > ncon[maxn];
int type[maxn];
void dfs(int x)
{
sz[x] = 1;
for (auto e : con[x])
{
int u = e.FF;
if (u==fa[x]) continue;
fa[u] = x;
len[u] = len[x]+e.SS;
lv[u] = lv[x]+1;
dfs(u);
sz[x] += sz[u];
if (!son[x]||sz[u]>sz[son[x]]) son[x] = u;
}
}
void dfs2(int x, int tp)
{
dfn[x] = ++dtot; arr[dtot] = x;
top[x] = tp;
if (son[x]) dfs2(son[x], tp);
for (auto e : con[x])
{
int u = e.FF;
if (u==fa[x]||u==son[x]) continue;
dfs2(u, u);
}
}
int get_lca(int x, int y)
{
while (true)
{
if (top[x]==top[y]) return arr[min(dfn[x], dfn[y])];
else
{
if (lv[top[x]]>lv[top[y]]) x = fa[top[x]];
else y = fa[top[y]];
}
}
}
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;
lv[1] = 1;
dfs(1);
dfs2(1, 1);
}
bool cmp(int x, int y) {return dfn[x]<dfn[y];}
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[])
{
vector<int> v;
for (int i=0; i<S; i++) v.PB(X[i]+1), type[X[i]+1] = 0;
for (int i=0; i<T; i++) v.PB(Y[i]+1), type[Y[i]+1] = 1;
sort(v.begin(), v.end(), cmp);
vector<int> st, all;
st.PB(v[0]); all.PB(v[0]);
for (int i=1; i<v.size(); i++)
{
int x = v[i];
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;
}
