#include "factories.h"
#include <bits/stdc++.h>
#define pb push_back
#define pf push_front
using namespace std;
#define F first
#define S second
typedef long long ll;
#define pii pair <int, int>
#define pll pair <ll, ll>
typedef long double ld;
const ll N = 5 * 1e5 + 100, M = 4096 + 10, len = 21, inf = 1e18;
const ll mod = 1e9 + 7;
ll um(ll a, ll b){
return (1LL * a * b) % mod;
}
ll subr(ll a, ll b){
return ((1LL * a - b) % mod + mod) % mod;
}
int n;
ll dis[N], sz[N], p[N];
vector <pll> q[N], boss[N];
bool was[N];
int dfs1(int v, int pred){
sz[v] = 1;
for(int i = 0; i < (int)q[v].size(); i++){
pll u = q[v][i];
if(u.F == pred) continue;
sz[v] += dfs1(u.F, v);
}
return sz[v];
}
int dfs2(int v, int pred = -1){
for(int i = 0; i < (int)q[v].size(); i++){
pll u = q[v][i];
if(u.F == pred || was[u.F]) continue;
if(sz[u.F] * 2 > sz[v]){
sz[v] -= sz[u.F];
sz[u.F] += sz[v];
return dfs2(u.F, v);
}
}
return v;
}
void dfs3(int v, int pred, int orig, ll sum){
boss[v].pb(make_pair(orig, sum));
for(int i = 0; i < (int)q[v].size(); i++){
pll u = q[v][i];
if(u.F == pred || was[u.F]) continue;
dfs3(u.F, v, orig, sum + u.S);
}
}
void centroid(int v, int pred = -1){
v = dfs2(v);
p[v] = pred;
was[v] = true;
dfs3(v, -1, v, 0LL);
for(int i = 0; i < (int)q[v].size(); i++){
pll u = q[v][i];
if(u.F == pred || was[u.F]) continue;
centroid(u.F, v);
}
}
void Init(int nx, int a[], int b[], int d[]) {
n = nx;
for(int i = 0; i < n; i++){
dis[i] = LLONG_MAX;
}
for(int i = 0; i < n - 1; i++){
q[a[i]].pb(make_pair(b[i], d[i]));
q[b[i]].pb(make_pair(a[i], d[i]));
}
dfs1(0, -1);
centroid(0);
}
long long Query(int s, int x[], int t, int y[]) {
// cout << "was\n";
for(int i = 0; i < s; i++){
for(int j = 0; j < (int)boss[x[i]].size(); j++){
pll u = boss[x[i]][j];
dis[u.F] = min(dis[u.F], u.S);
//cout << u.F << " "<< dis[u.F] << " Bosses\n";
}
}
ll ans = LLONG_MAX;
for(int i = 0; i < t; i++){
for(int j = 0; j < (int)boss[y[i]].size(); j++){
pll u = boss[y[i]][j];
if(dis[u.F] == LLONG_MAX) continue;
//cout << u.F << " "<< dis[u.F] << " "<< u.S << " Search answer\n";
ans = min(ans, dis[u.F] + u.S);
}
}
for(int i = 0; i < s; i++){
for(int j = 0; j < (int)boss[x[i]].size(); j++){
pll u = boss[x[i]][j];
dis[u.F] = LLONG_MAX;
}
}
return ans;
}
