#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include "factories.h"
#include <bits/stdc++.h>
#define ll long long
#define FOR(i,x,y) for(ll i=x; i<y; i++)
using namespace std;
bool r[600000];
vector<pair<ll,ll>> edges[600000];
ll sub[600000], par[600000], ans[600000];
ll n,m,root;
ll first[600000];
ll dists[600000];
vector<ll> euler;
vector<ll> updated;
void dfs2(ll a, ll p, ll v){
first[a] = euler.size();
euler.push_back(a);
for (auto&i : edges[a]){
if (i.first!=p){
dfs2(i.first, a, v+i.second);
euler.push_back(a);
}
}
dists[a] = v;
}
int distmin(ll a, ll b){
if (dists[a] < dists[b]){
return a;
}else{
return b;
}
}
int t[2*1048576];
void build() {
for (int i=1048576-1;i>0;--i)
t[i]=distmin(t[i<<1],t[i<<1|1]);
}
int query(int l,int r) {
int minV=0;
for (l+=1048576,r+=1048576;l<r;l>>=1,r>>=1) {
if (l&1){
minV=distmin(minV,t[l++]);
}
if (r&1){
minV=distmin(minV,t[--r]);
}
}
return minV;
}
ll dfs(ll a, ll p){
sub[a] = 1;
for (auto& i : edges[a]){
if (i.first!=p && !r[i.first]) sub[a] += dfs(i.first, a);
}
return sub[a];
}
ll centroid(ll a, ll sz, ll p){
for (auto&i : edges[a]){
if (i.first!=p && !r[i.first] && sub[i.first]*2 > sz){
return centroid(i.first, sz, a);
}
}
return a;
}
void decomp(ll a, ll p){
ll c = centroid(a, dfs(a, -1), -1);
if (p!=-1){
par[c] = p;
}else{
par[c] = -1;
}
r[c] = 1;
for (auto&i : edges[c]){
if (!r[i.first]) decomp(i.first, c);
}
}
ll dist(ll a, ll b){
if (first[a] > first[b]) swap(a,b);
return dists[a] + dists[b] - 2*dists[query(first[a],first[b])];
}
void update(ll a){
ll orig = a;
ans[a] = 0;
updated.push_back(a);
ll distance = 0;
while (par[a] != -1){
distance = dist(orig, par[a]);
a = par[a];
ans[a] = min(ans[a], distance);
updated.push_back(a);
}
}
ll query(ll a){
ll orig = a;
ll distance = 0;
ll tempans = 1000000000000000;
tempans = min(tempans, ans[a]);
while (par[a] != -1){
distance = dist(orig, par[a]);
a = par[a];
tempans = min(tempans, distance + ans[a]);
}
return tempans;
}
void Init(int N, int A[], int B[], int D[]) {
FOR(i,0,1048576) t[i] = 0;
FOR(i,0,600000) sub[i] = 0, r[i] = 0, ans[i] = 1000000000000000;
n = N;
dists[0] = 1000000000000000;
FOR(i,0,n-1){
ll a,b,c;
a = A[i]+1;
b = B[i]+1;
c = D[i];
edges[a].push_back({b,c});
edges[b].push_back({a,c});
}
dfs2(1,-1,0);
FOR(i,0,euler.size()){
t[i+1048576] = euler[i];
}
build();
decomp(1,-1);
}
long long Query(int S, int X[], int T, int Y[]) {
updated.clear();
ll anss = 1000000000000000;
FOR(i,0,S){
update(X[i]+1);
}
FOR(i,0,T){
anss = min(anss, (ll) query(Y[i]+1));
}
for (auto&i : updated){
ans[i] = 1000000000000000;
}
return anss;
}
