#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
struct sparse {
vector<vector<pair<int, int>>> arr;
int n;
void init(int sz, vector<pair<int, int>> x) {
n = sz;
arr.assign(n+2, vector<pair<int, int>>(22, {1e9, 1e9}));
for(int i=0; i<=sz; i++) {
arr[i][0] = x[i];
}
for(int i=1; i<=20; i++) {
for(int j=0; j+(1<<i)<=n; j++) {
arr[j][i] = min(arr[j][i-1], arr[j+(1<<(i-1))][i-1]);
}
}
}
int lca(int l, int r) {
int i = (int)log2(r-l+1);
return min(arr[l][i], arr[r-(1<<i)+1][i]).second;
}
};
struct tree {
vector<vector<pair<int, int>>> g;
vector<int> in, out, d;
vector<long long> td;
vector<pair<int, int>> arr;
int n, t;
sparse s;
void init(int sz, vector<vector<pair<int, int>>> graph) {
n = sz;
g = graph;
t = 0;
d.assign(n+2, 0);
td.assign(n+2, 0);
in.assign(n+2, 0);
out.assign(n+2, 0);
arr.assign(4*n+4, {1e18, 1e18});
dfs(1, -1, 0, 0);
for(int i=1; i<=n; i++) {
arr[in[i]] = {d[i], i};
}
s.init(t, arr);
}
void dfs(int no, int rt, int dis, long long tdis) {
in[no] = t;
arr[t] = {d[no], no};
t++;
d[no] = dis;
td[no] = tdis;
for(auto i: g[no]) {
if(i.first == rt) continue;
dfs(i.first, no, dis+1, tdis+i.second);
arr[t] = {d[no], no};
t++;
}
out[no] = t;
arr[t] = {d[no], no};
t++;
}
long long dist(int u, int v) {
if(in[u] > in[v]) swap(u, v);
return td[u]+td[v]-2*td[s.lca(in[u], in[v])];
}
};
tree tr;
struct cen {
vector<vector<pair<int, int>>> g;
vector<int> sz, cp, rem;
vector<long long> 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;
}
}
long long query(int u, int rt) {
long long 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(int N, int A[], int B[], int 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(int S, int X[], int T, int Y[]) {
for(int i=0; i<S; i++) {
cent.update(X[i]+1, X[i]+1);
}
long long 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;
}
