#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define fi first
#define se second
const int maxn = 5e5;
const ll inf = 1e16 + 42;
struct edge {
int to;
ll wei;
int subtree_size;
edge() : to(0), wei(0ll), subtree_size(0) {}
edge(int to_, ll wei_, int subtree_size_) :
to(to_), wei(wei_), subtree_size(subtree_size_) {}
};
const int logn = 20;
int n;
vector<edge > graph[1 + maxn];
bool done[1 + maxn];
vector<int> ctree[1 + maxn];
int cpar[1 + maxn];
int croot;
int dep[1 + maxn];
int lift[1 + maxn][logn];
ll pref[1 + maxn];
ll centdist[1 + maxn][logn];
int level[1 + maxn];
int dfs_subtree(int cur, int par, const int &all_size) {
int cur_size = 1;
for(edge &nei : graph[cur]) {
if(nei.to != par && !done[nei.to]) {
int this_size = dfs_subtree(nei.to, cur, all_size);
nei.subtree_size = this_size;
cur_size += this_size;
}
}
for(edge &nei : graph[cur]) {
if(nei.to == par) {
nei.subtree_size = all_size - cur_size;
break;
}
}
return cur_size;
}
void dfs_dist(int cur, int par, ll cur_dist, const int &cur_level) {
centdist[cur][cur_level] = cur_dist;
for(edge nei : graph[cur]) {
if(nei.to != par && !done[nei.to]) {
dfs_dist(nei.to, cur, cur_dist + nei.wei, cur_level);
}
}
}
void decompose(int cur, int prev_centroid, int all_size) {
dfs_subtree(cur, -1, all_size);
while(true) {
pii best = mp(-1, all_size / 2);
for(edge nei : graph[cur]) {
if(!done[nei.to]) {
pii cur_pair = mp(nei.to, nei.subtree_size);
if(cur_pair.se > best.se) {
best = cur_pair;
}
}
}
/*cout << cur << " " << prev_centroid << " " << all_size << endl;
for(edge e : graph[1]) {
cout << e.to << " " << e.subtree_size << endl;
}*/
if(best.fi == -1) {
break;
}
cur = best.fi;
}
// centroid: cur
cpar[cur] = prev_centroid;
if(prev_centroid != -1) {
ctree[prev_centroid].pb(cur);
level[cur] = level[cpar[cur]] + 1;
} else {
croot = cur;
}
dfs_dist(cur, -1, 0, level[cur]);
done[cur] = true;
for(edge nei : graph[cur]) {
if(!done[nei.to]) {
decompose(nei.to, cur, nei.subtree_size);
}
}
}
void dfs_depth(int cur) {
for(edge nei : graph[cur]) {
if(nei.to != lift[cur][0]) {
lift[nei.to][0] = cur;
dep[nei.to] = dep[cur] + 1;
pref[nei.to] = pref[cur] + nei.wei;
dfs_depth(nei.to);
}
}
}
int lca(int a, int b) {
if(dep[a] > dep[b]) {
swap(a, b);
}
for(int j = logn - 1; j >= 0; j--) {
if(dep[b] - (1 << j) >= dep[a]) {
b = lift[b][j];
}
}
if(a == b) {
return a;
}
for(int j = logn - 1; j >= 0; j--) {
if(lift[a][j] != lift[b][j]) {
a = lift[a][j];
b = lift[b][j];
}
}
return lift[b][0];
}
ll dist(int a, int b) {
int c = lca(a, b);
return pref[a] + pref[b] - 2 * pref[c];
}
ll nearest[1 + maxn];
bool to_reset[1 + maxn];
vector<int> reset;
void Init(signed N, signed A[], signed B[], signed D[]) {
n = N;
for(int i = 0; i < n - 1; i++) {
int a = A[i], b = B[i], d = D[i];
a++;
b++;
graph[a].pb(edge(b, d, 0));
graph[b].pb(edge(a, d, 0));
}
/*for(int i = 1; i <= n; i++) {
cout << i << endl;
for(edge e : graph[i]) {
cout << e.to << " " << e.wei << endl;
}
}
return;*/
decompose(1, -1, n);
lift[1][0] = 1;
dfs_depth(1);
for(int j = 1; j < logn; j++) {
for(int i = 1; i <= n; i++) {
lift[i][j] = lift[lift[i][j - 1]][j - 1];
}
}
for(int i = 1; i <= n; i++) {
nearest[i] = inf;
}
/*for(int i = 1; i <= n; i++) {
cout << cpar[i] << " ";
}
cout << endl;*/
}
void upd(int cur) {
int centroid = cur;
while(centroid != -1) {
if(!to_reset[centroid]) {
to_reset[centroid] = true;
reset.pb(centroid);
}
nearest[centroid] = min(nearest[centroid], centdist[cur][level[centroid]]);
centroid = cpar[centroid];
}
}
ll query(int cur) {
int centroid = cur;
ll res = inf;
while(centroid != -1) {
res = min(res, centdist[cur][level[centroid]] + nearest[centroid]);
centroid = cpar[centroid];
}
return res;
}
ll Query(signed S, signed X[], signed T, signed Y[]) {
vector<int> a, b;
for(int i = 0; i < S; i++) {
a.pb(X[i] + 1);
}
for(int j = 0; j < T; j++) {
b.pb(Y[j] + 1);
}
for(int y : b) {
upd(y);
}
ll ans = inf;
for(int x : a) {
ans = min(ans, query(x));
}
for(int r : reset) {
to_reset[r] = false;
nearest[r] = inf;
}
reset.clear();
return ans;
}
