#include "factories.h"
#include <bits/stdc++.h>
#define int long long
using namespace std;
struct tree {
vector<vector<pair<int, int>>> g;
vector<vector<int>> p;
vector<int> d, td;
int n;
void init(int sz, vector<vector<pair<int, int>>> graph) {
n = sz;
g = graph;
p.assign(n+2, vector<int>(32, 0));
d.assign(n+2, 0);
td.assign(n+2, 0);
dfs(1, -1, 0, 0);
for(int i=1; i<=30 ; i++) {
for(int j=1; j<=n; j++) {
p[j][i] = p[p[j][i-1]][i-1];
}
}
}
void dfs(int no, int rt, int dis, int tdis) {
d[no] = dis;
td[no] = tdis;
for(auto i: g[no]) {
if(i.first == rt) continue;
p[i.first][0] = no;
dfs(i.first, no, dis+1, tdis+i.second);
}
}
int lca(int u, int v) {
if(d[u] > d[v]) swap(u, v);
int dd = d[v]-d[u];
for(int i=30; i>=0; i--) {
if(dd & (1 << i)) {
v = p[v][i];
}
}
if(u == v) return u;
for(int i=30; i>=0; i--) {
if(p[u][i] != p[v][i]) {
u = p[u][i];
v = p[v][i];
}
}
return p[u][0];
}
int dist(int u, int v) {
return td[u]+td[v]-2*td[lca(u, v)];
}
};
tree tr;
struct cen {
vector<vector<pair<int, int>>> g;
vector<int> sz, cp, rem, val;
void init(int n, vector<vector<pair<int, int>>> graph) {
g = graph;
sz.assign(n+2, 0);
cp.assign(n+2, 0);
rem.assign(n+2, 0);
val.assign(n+2, 1e18);
build(1, -1);
}
int get_sz(int no, int rt) {
sz[no] = 1;
for(auto i: g[no]) {
if(i.first == rt || rem[i.first]) continue;
sz[no] += get_sz(i.first, no);
}
return sz[no];
}
int get_cent(int no, int rt, int siz) {
for(auto i: g[no]) {
if(i.first == rt || rem[i.first]) continue;
if(sz[i.first] > siz/2) return get_cent(i.first, no, siz);
}
return no;
}
void build(int no, int rt) {
int cent = get_cent(no, rt, get_sz(no, rt));
rem[cent] = 1;
if(rt == -1) cp[cent] = cent;
else cp[cent] = rt;
for(auto i: g[cent]) {
if(i.first == rt || rem[i.first]) continue;
build(i.first, cent);
}
}
void update(int u, int rt) {
val[rt] = min(val[rt], tr.dist(u, rt));
while(cp[rt] != rt) {
rt = cp[rt];
val[rt] = min(val[rt], tr.dist(u, rt));
}
}
void remove(int u, int rt) {
val[rt] = 1e18;
while(cp[rt] != rt) {
rt = cp[rt];
val[rt] = 1e18;
}
}
int query(int u, int rt) {
int ans = tr.dist(u, rt) + val[rt];
while(cp[rt] != rt) {
rt = cp[rt];
ans = min(ans, tr.dist(u, rt) + val[rt]);
}
return ans;
}
};
cen cent;
void Init(signed N, signed A[], signed B[], signed D[]) {
vector<vector<pair<int, int>>> g;
g.assign(N+2, vector<pair<int, int>>());
for(int i=0; i<N-1; i++) {
g[A[i]+1].push_back({B[i]+1, D[i]});
g[B[i]+1].push_back({A[i]+1, D[i]});
}
tr.init(N, g);
cent.init(N, g);
}
long long Query(signed S, signed X[], signed T, signed Y[]) {
for(int i=0; i<S; i++) {
cent.update(X[i]+1, X[i]+1);
}
int ans = 1e18;
for(int i=0; i<T; i++) {
ans = min(ans, cent.query(Y[i]+1, Y[i]+1));
}
for(int i=0; i<S; i++) {
cent.remove(X[i]+1, X[i]+1);
}
return ans;
}
