#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MAXN = 2e5+50;
#define INF 0x3f3f3f3f
#define INFLL 0x3f3f3f3f3f3f3f3f
#define optimize ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define endl "\n"
vector<vector<pair<int,int>>> g_adj(MAXN);
vector <int> sub(MAXN);
vector <bool> removed(MAXN);
vector<pair<int,ll>> dists_to_ancestor[MAXN]; // (centroid, distance)
int n,k1,k2;
ll answer = 0;
void dfs_store_distances(int u, int p, ll current_distance, int centroid){
dists_to_ancestor[u].push_back({centroid, current_distance});
for (auto &edge : g_adj[u]){
int v = edge.first;
int weight = edge.second;
if (v == p || removed[v]) continue;
dfs_store_distances(v, u, current_distance + weight, centroid);
}
}
int dfs_size(int u, int p){
sub[u] = 1;
for (auto &edge : g_adj[u]){
int v = edge.first;
if (v == p || removed[v]) continue;
sub[u] += dfs_size(v, u);
}
return sub[u];
}
int dfs_find_centroid(int u, int p, int n){
for (auto &edge : g_adj[u]){
int v = edge.first;
if (v == p || removed[v]) continue;
if (sub[v] > n/2) return dfs_find_centroid(v, u, n);
}
return u;
}
void decompose(int start){
int n_comp = dfs_size(start, -1);
int centroid = dfs_find_centroid(start, -1, n_comp);
dfs_store_distances(centroid, -1, 0, centroid); // Store distances to this centroid
removed[centroid] = true;
for (auto &edge : g_adj[centroid]){
int v = edge.first;
if (!removed[v]) decompose(v);
}
}
long long Query(int S, int X[], int T, int Y[]){
unordered_map<int,ll> dist_to_y;
for (int i=0;i<T;i++){
int node = Y[i] - 1;
for (auto &pr :dists_to_ancestor[node]){
int centroid = pr.first;
ll distance = pr.second;
if (dist_to_y.find(centroid) == dist_to_y.end()){
dist_to_y[centroid] = distance;
} else {
dist_to_y[centroid] = min(dist_to_y[centroid], distance);
}
}
}
ll min_distance = INFLL;
for (int i=0;i<S;i++){
int node = X[i] - 1;
for (auto &pr :dists_to_ancestor[node]){
int centroid_ancestor = pr.first;
ll distance_to_ancestor = pr.second;
if (dist_to_y.find(centroid_ancestor) != dist_to_y.end()){
ll total_distance = distance_to_ancestor + dist_to_y[centroid_ancestor];
min_distance = min(min_distance, total_distance);
}
}
}
if (min_distance == INFLL) return -1;
return min_distance;
}
void Init(int N, int A[], int B[], int D[]) {
n = N;
for (int i=0;i<n-1;i++){
int u = A[i];
int v = B[i];
int w = D[i];
u--;v--;
g_adj[u].push_back({v,w});
g_adj[v].push_back({u,w});
}
decompose(0);
}
/*
void solve(){
cin >> n >> k1 >> k2;
for (int i=0; i<n-1; i++){
int u,v;
cin >> u >> v;
--u; --v;
g_adj[u].push_back(v);
g_adj[v].push_back(u);
}
decompose(0);
cout << answer << endl;
}
int main (){
optimize;
solve();
return 0;
}
*/
