#include<bits/stdc++.h>
#include "factories.h"
using namespace std;
const int MAXN = 500010;
const int MAXK = 21;
const long long int INF = 2e18;
int n, q, n_cur, sub[MAXN], par[MAXN], depth[MAXN];
long long int dist[MAXK][MAXN];
vector<int> graph[MAXN], cost[MAXN];
set<long long int> s[MAXN];
bool marc[MAXN];
void find_sub(int v, int p)
{
sub[v] = 1;
for(int i = 0; i < (int) graph[v].size(); i++)
{
int u = graph[v][i];
if(u == p || marc[u]) continue;
find_sub(u, v), sub[v] += sub[u];
}
}
int find_centroid(int v, int p)
{
for(int i = 0; i < (int) graph[v].size(); i++)
{
int u = graph[v][i];
if(u == p || marc[u]) continue;
if(2 * sub[u] >= n_cur) return find_centroid(u, v);
}
return v;
}
void find_dist(int v, int p, int l, long long int d)
{
dist[l][v] = d;
// printf("dist[%d][%d] = %lld\n", l, v, dist[l][v]);
for(int i = 0; i < (int) graph[v].size(); i++)
{
int u = graph[v][i];
int w = cost[v][i];
if(u == p || marc[u]) continue;
find_dist(u, v, l, d + w);
}
}
void decompose(int v, int p, int level)
{
find_sub(v, p);
n_cur = sub[v];
int centroid = find_centroid(v, p);
// printf("centroid = %d\n", centroid);
marc[centroid] = true;
par[centroid] = (v == p) ? centroid : p;
depth[centroid] = level;
find_dist(centroid, centroid, level, 0);
for(int i = 0; i < (int) graph[centroid].size(); i++)
{
int u = graph[centroid][i];
if(!marc[u]) decompose(u, centroid, level + 1);
}
}
void Init(int N, int A[], int B[], int D[])
{
n = N;
for(int i = 0; i < n - 1; i++)
{
int a = A[i], b = B[i], d = D[i];
graph[a].push_back(b);
graph[b].push_back(a);
cost[a].push_back(d);
cost[b].push_back(d);
}
decompose(0, 0, 0);
}
void upd(int v, bool flag)
{
int cur = v;
if(flag) s[cur].insert(0);
else s[cur].clear();
while(cur != par[cur])
{
cur = par[cur];
if(flag) s[cur].insert(dist[depth[cur]][v]);
else s[cur].clear();
}
}
long long int qry(int v)
{
int cur = v;
long long int ans = (s[cur].empty()) ? INF : *s[cur].begin();
while(cur != par[cur])
{
cur = par[cur];
ans = min(ans, (s[cur].empty()) ? INF : *s[cur].begin() + dist[depth[cur]][v]);
}
return ans;
}
long long int Query(int S, int X[], int T, int Y[])
{
for(int i = 0; i < S; i++) upd(X[i], true);
long long int ans = INF;
for(int i = 0; i < T; i++) ans = min(ans, qry(Y[i]));
for(int i = 0; i < S; i++) upd(X[i], false);
return ans;
}
