#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
#define st first
#define nd second
typedef long long ll;
constexpr int LIM = 5e5;
vector<pair<int, int> >g[LIM + 10];
unordered_map<int, ll>dist[LIM + 10];
ll cnt[LIM + 10];
int siz[LIM + 10];
int oj[LIM + 10];
bool vis[LIM + 10];
void cntsiz(int v, int o) {
siz[v] = 1;
for(auto x : g[v]) {
if(x.st != o) {
cntsiz(x.st, v);
siz[v] += siz[x.st];
}
}
}
void cntdist(int v, int o, int kt) {
for(auto x : g[v]) {
if(x.st != o && !vis[x.st]) {
dist[kt][x.st] = dist[kt][v] + x.nd;
cntdist(x.st, v, kt);
}
}
}
int find(int a) {
for(auto x : g[a]) {
if(!vis[x.st] && siz[x.st] > siz[a] / 2) {
int tmp = siz[x.st];
siz[x.st] = siz[a];
siz[a] -= tmp;
return find(x.st);
}
}
return a;
}
void dfs(int v, int o) {
int c = find(v);
oj[c] = o;
vis[c] = 1;
cntdist(c, c, c);
for(auto x : g[c]) {
if(!vis[x.st]) {
dfs(x.st, c);
}
}
}
void Init(int n, int a[], int b[], int c[]) {
for(int i = 0; i < n - 1; i++) {
g[a[i]].push_back({b[i], c[i]});
g[b[i]].push_back({a[i], c[i]});
}
for(int i = 0; i < n; i++) {
cnt[i] = 1e18;
}
cntsiz(1, 1);
dfs(1, -1);
}
ll Query(int n, int a[], int m, int b[]) {
vector<int>vs;
for(int i = 0; i < n; i++) {
int tmp = a[i];
while(tmp != -1) {
cnt[tmp] = min(cnt[tmp], dist[tmp][a[i]]);
vs.push_back(tmp);
tmp = oj[tmp];
}
}
ll ans = 1e18;
for(int i = 0; i < m; i++) {
int tmp = b[i];
while(tmp != -1) {
ans = min(ans, cnt[tmp] + dist[tmp][b[i]]);
tmp = oj[tmp];
}
}
for(auto x : vs) {
cnt[x] = 1e18;
}
return ans;
}
