#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define ar array
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template <typename T> using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define vt vector
#define rsz resize
#define pb push_back
#define eb emplace_back
#define all(c) (c).begin(), (c).end()
#define sz(x) (int)(x).size()
#define pll pair<ll, ll>
#define pii pair<int, int>
#define f first
#define s second
#define F_OR(i, a, b, s) for (int i=(a); (s)>0?i<(b):i>(b); i+=(s))
#define F_OR1(e) F_OR(i, 0, e, 1)
#define F_OR2(i, e) F_OR(i, 0, e, 1)
#define F_OR3(i, b, e) F_OR(i, b, e, 1)
#define F_OR4(i, b, e, s) F_OR(i, b, e, s)
#define GET5(a, b, c, d, e, ...) e
#define F_ORC(...) GET5(__VA_ARGS__, F_OR4, F_OR3, F_OR2, F_OR1)
#define FOR(...) F_ORC(__VA_ARGS__)(__VA_ARGS__)
#define EACH(x, a) for (auto& x: a)
template<class T> bool umin(T& a, const T& b) {
return b<a?a=b, 1:0;
}
template<class T> bool umax(T& a, const T& b) {
return a<b?a=b, 1:0;
}
ll FIRSTTRUE(function<bool(ll)> f, ll lb, ll rb) {
while(lb<rb) {
ll mb=(lb+rb)/2;
f(mb)?rb=mb:lb=mb+1;
}
return lb;
}
ll LASTTRUE(function<bool(ll)> f, ll lb, ll rb) {
while(lb<rb) {
ll mb=(lb+rb+1)/2;
f(mb)?lb=mb:rb=mb-1;
}
return lb;
}
template<class A> void read(vt<A>& v);
template<class A, size_t S> void read(ar<A, S>& a);
template<class A, class B> void read(pair<A, B>& x);
template<class T> void read(T& x) {
cin >> x;
}
void read(double& d) {
string t;
read(t);
d=stod(t);
}
void read(long double& d) {
string t;
read(t);
d=stold(t);
}
template<class H, class... T> void read(H& h, T&... t) {
read(h);
read(t...);
}
template<class A> void read(vt<A>& x) {
EACH(a, x)
read(a);
}
template<class A, size_t S> void read(array<A, S>& x) {
EACH(a, x)
read(a);
}
template<class A, class B> void read(pair<A, B>& x) {
cin >> x.first >> x.second;
}
string to_string(char c) {
return string(1, c);
}
string to_string(bool b) {
return b?"true":"false";
}
string to_string(const char* s) {
return string(s);
}
string to_string(string s) {
return s;
}
string to_string(vt<bool> v) {
string res;
FOR(sz(v))
res+=char('0'+v[i]);
return res;
}
template<size_t S> string to_string(bitset<S> b) {
string res;
FOR(S)
res+=char('0'+b[i]);
return res;
}
template<class T> string to_string(T v) {
bool f=1;
string res;
EACH(x, v) {
if(!f)
res+=' ';
f=0;
res+=to_string(x);
}
return res;
}
template<class A, class B> string to_string(pair<A, B>& x) {
return to_string(x.first) + ' ' + to_string(x.second);
}
template<class A> void write(A x) {
cout << to_string(x);
}
template<class H, class... T> void write(const H& h, const T&... t) {
write(h);
write(t...);
}
void print() {
write("\n");
}
template<class H, class... T> void print(const H& h, const T&... t) {
write(h);
if(sizeof...(t))
write(' ');
print(t...);
}
template<typename T>
struct RMQ {
int level(int x) { return 31-__builtin_clz(x); }
vt<T> v; vt<vt<int>> jmp;
int cmb(int a, int b) {
return v[a]==v[b]?min(a,b):(v[a]<v[b]?a:b); }
void init(const vt<T>& _v) {
v = _v; jmp = {vt<int>(sz(v))};
iota(all(jmp[0]),0);
for (int j = 1; 1<<j <= sz(v); ++j) {
jmp.pb(vt<int>(sz(v)-(1<<j)+1));
FOR(i,sz(jmp[j])) jmp[j][i] = cmb(jmp[j-1][i],
jmp[j-1][i+(1<<(j-1))]);
}
}
int index(int l, int r) {
assert(l <= r); int d = level(r-l+1);
return cmb(jmp[d][l],jmp[d][r-(1<<d)+1]); }
T query(int l, int r) { return v[index(l,r)]; }
};
struct LCA {
int N; vt<vt<int>> adj;
vt<int> depth, pos, par, rev;
vt<pii> tmp; RMQ<pii> r;
void init(int _N) { N = _N; adj.resize(N);
depth = pos = par = rev = vt<int>(N); }
void ae(int x, int y) { adj[x].pb(y), adj[y].pb(x); }
void dfs(int x) {
pos[x] = sz(tmp); tmp.eb(depth[x],x);
EACH(y,adj[x]) if (y != par[x]) {
depth[y] = depth[par[y]=x]+1, dfs(y);
tmp.eb(depth[x],x); }
}
void gen(int R = 0) { par[R] = R; dfs(R); r.init(tmp); }
int lca(int u, int v){
u = pos[u], v = pos[v]; if (u > v) swap(u,v);
return r.query(u,v).s; }
int dist(int u, int v) {
return depth[u]+depth[v]-2*depth[lca(u,v)]; }
vt<pii> compress(vt<int> S) {
auto cmp = [&](int a, int b) { return pos[a] < pos[b]; };
sort(all(S),cmp); FOR(i,sz(S)-1,-1,-1) S.pb(lca(S[i],S[i+1]));
sort(all(S),cmp); S.erase(unique(all(S)),end(S));
vt<pii> ret{{0,S[0]}}; FOR(i,sz(S)) rev[S[i]] = i;
FOR(i,1,sz(S)) ret.eb(rev[lca(S[i-1],S[i])],S[i]);
return ret;
}
};
vt<vt<pii>> wadj;
vt<vt<int>> adj, cadj;
vt<bool> vis;
vt<int> dsz, par;
vt<ll> d, dp;
LCA lca;
ll dist(int a, int b) {
int c=lca.lca(a, b);
return d[a]+d[b]-2*d[c];
}
int dfsz(int v, int p=-1) {
dsz[v]=1;
EACH(u, adj[v]) {
if (!vis[u] && u!=p) {
dsz[v]+=dfsz(u, v);
}
}
return dsz[v];
}
int dfsc(int v, int tsz, int p=-1) {
EACH(u, adj[v]) {
if (!vis[u] && u!=p && dsz[u]>tsz/2) {
return dfsc(u, tsz, v);
}
}
return v;
}
int centroid(int v=0, int p=-1) {
int c=dfsc(v, dfsz(v), p);
vis[c]=1;
if (p!=-1) cadj[p].pb(c);
EACH(u, adj[c]) {
if (!vis[u]) {
centroid(u, c);
}
}
return c;
}
void dfsog(int v, int p=-1) {
EACH(e, wadj[v]) {
if (e.f!=p) {
d[e.f]=d[v]+e.s;
dfsog(e.f, v);
}
}
}
void dfs(int v, int p=-1) {
par[v]=p;
EACH(u, cadj[v]) {
dfs(u, v);
}
}
void Init(int n, int a[], int b[], int w[]) {
adj.rsz(n), wadj.rsz(n), cadj.rsz(n), vis.assign(n, 0), dsz.rsz(n), d.rsz(n), par.rsz(n), dp.assign(n, 1e18);
lca.init(n);
FOR(n-1) {
wadj[a[i]].pb({b[i], w[i]}), wadj[b[i]].pb({a[i], w[i]});
adj[a[i]].pb(b[i]), adj[b[i]].pb(a[i]);
lca.ae(a[i], b[i]);
}
lca.gen();
d[0]=0;
dfsog(0);
int c=centroid();
dfs(c);
}
void update(int v) {
int t=v;
for (; v!=-1; v=par[v]) umin(dp[v], dist(t, v));
}
void reset(int v) {
for (; v!=-1 && dp[v]!=1e18; v=par[v]) dp[v]=1e18;
}
ll query(int v) {
ll ret=LLONG_MAX;
int t=v;
for (; v!=-1; v=par[v]) umin(ret, dist(t, v)+dp[v]);
return ret;
}
ll Query(int n, int x[], int m, int y[]) {
ll ret=LLONG_MAX;
FOR(n) update(x[i]);
FOR(m) umin(ret, query(y[i]));
FOR(n) reset(x[i]);
return ret;
}
