#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
const int MX=500010, LG=20;
const ll inf=2e17;
struct edge {
int to; ll co;
};
int n, dep[MX];
vector<edge> G[MX];
vector<edge> C, D[MX];
bool done[MX];
int sub[MX];
void dfs(int v, int p=-1){
sub[v]=1;
for(edge &e:G[v]){
int x=e.to;
if(done[x] || x==p) continue;
dfs(x,v);
sub[v]+=sub[x];
}
}
int findcen(int v, int sz){
for(edge &e:G[v]){
int x=e.to;
if(done[x] || sub[x]>sub[v]) continue;
if(sub[x]*2>sz) return findcen(x,sz);
}
return v;
}
void dfs2(int v, int p, ll d){
C.push_back({v,d});
for(edge &e:G[v]){
int x=e.to; ll c=e.co;
if(done[x] || x==p) continue;
dfs2(x,v,d+c);
}
}
ll mn1[MX], mn2[MX];
void process(int v=1){
dfs(v,0);
v=findcen(v,sub[v]); done[v]=true;
for(edge &e:G[v]){
int x=e.to; ll c=e.co;
if(done[x]) continue;
dfs2(x,v,c);
}
C.push_back({v,0});
for(edge &e:C){
int x=e.to; ll c=e.co;
D[x].push_back({v,c});
}
C.clear();
for(edge &e:G[v]){
int x=e.to;
if(done[x]) continue;
process(x);
}
}
void Init(int N, int A[], int B[], int D[]){
n=N;
fill(mn1, mn1+n+1, inf);
fill(mn2, mn2+n+1, inf);
for(int i=0; i<=n-2; i++){
int u=A[i]+1, v=B[i]+1;
G[u].push_back({v,D[i]});
G[v].push_back({u,D[i]});
}
process();
}
ll Query(int S, int X[], int T, int Y[]) {
for(int i=0; i<S; i++) X[i]++;
for(int i=0; i<T; i++) Y[i]++;
vector<int> V, W;
for(int i=0; i<S; i++){
for(edge &e:D[X[i]])
V.push_back(e.to), mn1[e.to]=min(mn1[e.to], e.co);
}
for(int i=0; i<T; i++){
for(edge &e:D[Y[i]])
W.push_back(e.to), mn2[e.to]=min(mn2[e.to], e.co);
}
ll ans=inf;
for(int v:V) ans=min(ans, mn1[v]+mn2[v]);
for(int w:W) ans=min(ans, mn1[w]+mn2[w]);
for(int v:V) mn1[v]=inf;
for(int w:W) mn2[w]=inf;
return ans;
}
