#include <bits/stdc++.h>
using namespace std;
#include "factories.h"
// #define int long long
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define pb push_back
#define all(a) a.begin(), a.end()
#define endl "\n"
void printVector(vector<int> a){
for (auto x: a) cout << x << " ";
cout << endl;
}
int min(int x, int y){
if (x < y) return x;
return y;
}
vector<vector<pair<int, int>>> graph;
vector<int> depth;
vector<vector<int>> up;
vector<int> ctree;
vector<int> subtree;
vector<int> vis(100000);
vector<long long> d;
vector<long long> ans;
int L = 0;
int C = 1;
int dp(int x, int p = -1){
if (vis[x]) return 0;
subtree[x] = 1;
for (auto [node, w]: graph[x]){
if (node == p) continue;
subtree[x] += dp(node, x);
}
return subtree[x];
}
int find_centroid(int x, int p, int n){
for (auto [node, w]: graph[x]){
if (node == p) continue;
if (!vis[node] && subtree[node]*2 > n) return find_centroid(node, x, n);
}
return x;
}
void init_centroid(int x = 1, int p = -1){
dp(x);
int c = find_centroid(x, -1, subtree[x]);
vis[c] = 1;
ctree[c] = p;
for (auto [node, w]: graph[c]){
if (!vis[node]){
init_centroid(node, c);
}
}
}
int lca(int x, int y){
if (depth[x] < depth[y]) swap(x, y);
int k = depth[x]-depth[y];
for (int i = L-1; i >= 0; i--){
if (k & (1 << i)) x = up[x][i];
}
if (x == y) return x;
for (int i = L-1; i >= 0; i--){
if (up[x][i] != up[y][i]){
x = up[x][i];
y = up[y][i];
}
}
return up[x][0];
}
long long dist(int x, int y){
return d[x]+d[y]-(2ll)*d[lca(x, y)];
}
void update(int x, int t){
int k = x;
ans[x] = 0;
while (k != -1){
if (t == 0) ans[k] = min(ans[k], ans[x]+dist(x, k));
else ans[k] = 1e16;
k = ctree[k];
}
}
long long query(int x){
long long e = 1e16;
int k = x;
while (k != -1){
e = min(e, ans[k]+dist(x, k));
k = ctree[k];
}
return e;
}
void Init(int N, int A[], int B[], int D[]) {
int n = N;
graph.resize(n+1);
subtree.resize(n+1);
ans.resize(n+1, 1e16);
L = log2(n)+1;
vis.resize(n+1);
depth.resize(n+1);
d.resize(n+1);
ctree.resize(n+1);
up.resize(n+1, vector<int>(L));
FOR(i,0,n-1){
graph[A[i]].pb({B[i], D[i]});
graph[B[i]].pb({A[i], D[i]});
}
vector<int> visited(n+1);
stack<int> s;
s.push(0);
while (!s.empty()){
int current = s.top();
s.pop();
if (visited[current]) continue;
for (auto x: graph[current]){
if (visited[x.first]) continue;
d[x.first] = d[current]+x.second;
depth[x.first] = depth[current]+1;
up[x.first][0] = current;
s.push(x.first);
}
visited[current] = 1;
}
for (int i = 1; i < L; i++){
for (int j = 1; j <= n; j++) up[j][i] = up[ up[j][i-1] ][i-1];
}
C = find_centroid(0, -1, n);
init_centroid();
}
long long Query(int S, int X[], int T, int Y[]) {
long long ANS = 1e16;
FOR(i,0,S){
update(X[i], 0);
}
FOR(i,0,T){
ANS = min(ANS, query(Y[i]));
}
FOR(i,0,S){
update(X[i], 1);
}
return ANS;
}
