#include "factories.h"
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <tuple>
using namespace std;
#define REP(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define REPO(i,n) for(int (i)=1; (i)<=(int)(n); (i)++)
#define SZ(v) ((int)(v).size())
#define ALL(v) (v).begin(),(v).end()
#define one first
#define two second
typedef long long ll;
typedef pair<int, int> pi;
const int INF = 0x3f2f1f0f;
const ll LINF = 1ll * INF * INF;
const int MAX_N = 5e5 + 100, LOG_N = 20;
int N; bool cChk[MAX_N];
vector<pi> Ed[MAX_N];
int S[MAX_N];
int getS(int v, int p) {
S[v] = 1;
for(pi &e : Ed[v]) {
int w, d; tie(w, d) = e;
if(w == p || cChk[w]) continue;
S[v] += getS(w, v);
}
return S[v];
}
int findC(int v, int p, int all) {
for(pi &e : Ed[v]) {
int w, d; tie(w, d) = e;
if(w == p || cChk[w]) continue;
if(S[w] > all / 2) return findC(w, v, all);
}
return v;
}
int D[MAX_N], cP[MAX_N]; ll Len[LOG_N][MAX_N];
void getLen(int v, int p, int dep, ll dis) {
Len[dep][v] = dis;
// printf("%d %d = %lld\n", dep, v, dis);
for(pi &e : Ed[v]) {
int w, d; tie(w, d) = e;
if(w == p || cChk[w]) continue;
getLen(w, v, dep, dis+d);
}
}
int cDfs(int v, int dep) {
v = findC(v, 0, getS(v, 0));
D[v] = dep;
cChk[v] = true;
getLen(v, 0, dep, 0ll);
// printf("%d(th) : %d (%d)\n", dep, v, S[v]);
for(pi &e : Ed[v]) {
int w, d; tie(w, d) = e;
if(cChk[w]) continue;
cP[cDfs(w, dep+1)] = v;
}
return v;
}
void Init(int n, int a[], int b[], int d[]) {
N = n;
REP(i, N-1) {
a[i]++; b[i]++;
Ed[a[i]].push_back(pi(b[i], d[i]));
Ed[b[i]].push_back(pi(a[i], d[i]));
}
cDfs(1, 0);
}
int lastQ[MAX_N], Q; ll minQ[MAX_N];
long long Query(int S, int X[], int T, int Y[]) {
Q++;
REP(i, S) {
int s = X[i] + 1;
for(int v = s, d = D[v]; v; v = cP[v], d--)
if(lastQ[v] != Q || minQ[v] > Len[d][s])
lastQ[v] = Q, minQ[v] = Len[d][s];
}
ll ans = LINF;
REP(i, T) {
int t = Y[i] + 1;
for(int v = t, d = D[v]; v; v = cP[v], d--)
if(lastQ[v] == Q) {
ans = min(ans, minQ[v] + Len[d][t]);
}
}
return ans;
}
