#include "factories.h"
#include <bits/stdc++.h>
#define ll long long
#define X first
#define Y second
#define MP make_pair
using namespace std;
const int N = 5e5 + 2;
const ll INF = 1e18;
int lg[N * 4];
int n, sz[N], mx[N], block[N], cent_pr[N], depth[N], ord[21][N * 4], timer, tin[N];
ll dp[N], mcost[N];
int last_used[N], Q;
vector< pair< int, int > > g[N];
void dfs_sz(int v, int pr){
sz[v] = 1, mx[v] = 0;
for(pair<int, int> to: g[v]){
if(to.X == pr || block[to.X])
continue;
dfs_sz(to.X, v), sz[v] += sz[to.X];
mx[v] = (sz[mx[v]] < sz[to.X] ? to.X: mx[v]);
}
}
int get_cent(int v){
int u = v;
while(sz[mx[u]] * 2 > sz[v])
u = mx[u];
return u;
}
void cent(int v, int pr){
dfs_sz(v, v), v = get_cent(v);
cent_pr[v] = pr, block[v] = 1;
for(pair<int, int> to: g[v]){
if(!block[to.X])
cent(to.X, v);
}
}
void dfs_prep(int v, int pr){
tin[v] = ++timer, ord[0][timer] = v;
for(pair<int, int> to: g[v]){
if(to.X == pr)
continue;
dp[to.X] = dp[v] + to.Y, depth[to.X] = depth[v] + 1;
dfs_prep(to.X, v);
ord[0][++timer] = v;
}
}
ll calc(int x, int y){
if(tin[x] > tin[y])
swap(x, y);
int mid = (tin[y] - tin[x] + 1);
mid = (depth[ord[lg[mid]][tin[x]]] < depth[ord[lg[mid]][tin[y] - (1 << lg[mid]) + 1]] ? ord[lg[mid]][tin[x]]: ord[lg[mid]][tin[y] - (1 << lg[mid]) + 1]);
// cerr << x - 1 << " " << y - 1 << " " << mid - 1 << "\n";
return dp[x] + dp[y] - 2 * dp[mid];
}
void Init(int N2, int A[], int B[], int D[]) {
for(int i = 2;i < N * 4;i++)
lg[i] = lg[i / 2] + 1;
n = N2;
for(int i = 0;i < n - 1;i++){
g[A[i] + 1].push_back(MP(B[i] + 1, D[i]));
g[B[i] + 1].push_back(MP(A[i] + 1, D[i]));
}
cent(1, 0);
dfs_prep(1, 1);
for(int i = 1;i <= 20;i++)
for(int j = 1;j + (1 << i) - 1 <= timer;j++)
ord[i][j] = (depth[ord[i - 1][j]] < depth[ord[i - 1][j + (1 << (i - 1))]] ? ord[i - 1][j]: ord[i - 1][j + (1 << (i - 1))]);
}
long long Query(int S, int X[], int T, int Y[]) {
// cerr << "NEXT\n";
ll ans = INF;
Q++;
for(int i = 0;i < S;i++){
X[i]++;
int j = X[i];
while(j){
if(last_used[j] != Q)
last_used[j] = Q, mcost[j] = INF;
mcost[j] = min(mcost[j], calc(j, X[i]));
// cerr << j - 1 << " " << X[i - 1] << " " << calc(j, X[i]) << "\n";
j = cent_pr[j];
}
}
for(int i = 0;i < T;i++){
Y[i]++;
int j = Y[i];
while(j){
if(last_used[j] != Q)
last_used[j] = Q, mcost[j] = INF;
ans = min(ans, mcost[j] + calc(j, Y[i]));
// cerr << j - 1 << " " << Y[i] - 1 << " " << ans << " " << mcost[j] << " " << calc(j, Y[i]) << "\n";
j = cent_pr[j];
}
}
return ans;
}
