#include<bits/stdc++.h>
#include "factories.h"
#define s second
#define f first
#define pii pair<int, long long>
using namespace std;
using ll = long long;
const int maxn = 5e5 + 1;
bool removed[maxn] {};
int sz[maxn] {};
vector<pii> adj[maxn];
int get_sz(int u, int p) {
sz[u] = 1;
for(pii P : adj[u]) {
int v = P.f;
if(removed[v] || v == p) continue;
sz[u] += get_sz(v, u);
}
return sz[u];
}
int get_centroid(int u, int p, int sze) {
for(pii P : adj[u]) {
int v = P.f;
if(removed[v] || v == p) continue;
if(sz[v] > sze / 2) return get_centroid(v, u, sze);
}
return u;
}
vector<pii> anc[maxn];
void get_dist(int u, int p, int cent, ll dist) {
for(pii P : adj[u]) {
int v = P.f;
ll w = P.s;
if(removed[v] || v == p) continue;
get_dist(v, u, cent, dist + w);
}
anc[u].push_back({cent, dist});
}
int build_centroid(int u) {
get_sz(u, -1);
int center = get_centroid(u, -1, sz[u]);
removed[center] = 1;
anc[center].push_back({center, 0});
for(pii P : adj[center]) {
int v = P.f;
ll w = P.s;
if(removed[v]) continue;
get_dist(v, center, center, w);
}
for(pii P : adj[center]) {
int v = P.f;
if(removed[v]) continue;
build_centroid(v);
}
return center;
}
vector<ll> dist(maxn, 1e18);
void Init(int N, int A[], int B[], int D[]) {
for(int i = 0; i < N - 1; i++) {
adj[A[i]].push_back({B[i], 1LL * D[i]});
adj[B[i]].push_back({A[i], 1LL * D[i]});
}
int center = build_centroid(0);
}
long long Query(int S, int X[], int T, int Y[]) {
ll ans = 1e18;
for(int i = 0; i < S; i++) {
for(pii P : anc[X[i]]) {
int v = P.f;
ll w = P.s;
dist[v] = 1e18;
}
}
for(int i = 0; i < T; i++) {
for(pii P : anc[Y[i]]) {
int v = P.f;
ll w = P.s;
dist[v] = min(dist[v], w);
}
}
for(int i = 0; i < S; i++) {
for(pii P : anc[X[i]]) {
int v = P.f;
ll w = P.s;
ans = min(ans, dist[v] + w);
}
}
return ans;
}
//void Init(int N, vector<int> A, vector<int> B, vector<int> D) {
// for(int i = 0; i < N - 1; i++) {
// adj[A[i]].push_back({B[i], 1LL * D[i]});
// adj[B[i]].push_back({A[i], 1LL * D[i]});
// }
// int center = build_centroid(0);
//}
//
//ll Query(int S, vector<int> X, int T, vector<int> Y) {
// ll ans = 1e18;
// for(int i = 0; i < S; i++) {
// for(pii P : anc[X[i]]) {
// int v = P.f;
// ll w = P.s;
// dist[v] = 1e18;
// }
// }
// for(int i = 0; i < T; i++) {
// for(pii P : anc[Y[i]]) {
// int v = P.f;
// ll w = P.s;
// dist[v] = min(dist[v], w);
// }
// }
// for(int i = 0; i < S; i++) {
// for(pii P : anc[X[i]]) {
// int v = P.f;
// ll w = P.s;
// ans = min(ans, dist[v] + w);
// }
// }
// return ans;
//}
//int main() {
// ios::sync_with_stdio(0);
// cin.tie(0);
// Init(7, {0, 1, 2, 2, 4, 1}, {1, 2, 3, 4, 5, 6}, {4, 4, 5, 6, 5, 3});
// cout << Query(1, {0}, 1, {6}) << '\n';
// return 0;
//}
