#include <bits/stdc++.h>
#include "factories.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define debug(...) fprintf(stderr, __VA_ARGS__)
//#define debug(...)
#define fi first
#define se second
#define all(v) (v).begin(), (v).end()
#define fillchar(a, s) memset((a), (s), sizeof(a))
const int MAXN = 5e5 + 10;
const int MAXLG = 19;
const ll INF = 1e16;
void setmin (ll &a, ll b) {
if (a > b) {
a = b;
}
}
int N;
vector<pll> adj[MAXN];
ll ans[MAXN];
int sz[MAXN];
bool vis[MAXN];
int dfssz (int x, int p) {
sz[x] = 1;
for (auto py : adj[x]) {
int y = py.fi;
if (y != p && !vis[y]) {
sz[x] += dfssz(y, x);
}
}
return sz[x];
}
int findcent (int x, int p, int s) {
for (auto py : adj[x]) {
int y = py.fi;
if (y != p && !vis[y]) {
return findcent(y, x, s);
}
}
return x;
}
int par[MAXN];
int hcent[MAXN];
ll dist[20][MAXN];
//Note: here, you are not actually dfsing through centroid tree - you are dfsing through the original tree.
void dfslow (int x, int p, int h, ll w) {
dist[h][x] = w;
for (pll py : adj[x]) {
int y = py.fi;
if (y != p && !vis[y]) {
dfslow(y, x, h, w + py.se);
}
}
}
void dfsc (int x, int pc) {
int szcmp = dfssz(x, -1);
x = findcent(x, -1, szcmp);
vis[x] = true;
par[x] = pc;
if (pc != -1) {
hcent[x] = hcent[pc] + 1;
}
dfslow(x, -1, hcent[x], 0ll); //dfs to unvisited vertices - or "low" vertices (in the subtree).
for (auto py : adj[x]) {
int y = py.fi;
if (y != pc && !vis[y]) {
dfsc(y, x);
}
}
}
void update (int x, bool reset) {
exit(0);
for (int i = x; i != -1; i = par[i]) {
debug("i = %d\n", i);
if (reset) {
ans[i] = INF;
} else {
setmin(ans[i], dist[hcent[i]][x]);
}
}
}
ll query (int x) {
ll res = INF;
for (int i = x; i != -1; i = par[i]) {
setmin(res, ans[i] + dist[hcent[i]][x]);
}
return res;
}
void Init (int nn, int a[], int b[], int d[]) {
N = nn;
for (int i = 0; i < N - 1; i++) {
adj[a[i]].push_back(pll(b[i], d[i]));
adj[b[i]].push_back(pll(a[i], d[i]));
}
for (int i = 0; i < N; i++) {
ans[i] = INF;
}
dfsc(0, -1);
}
ll Query (int S, int X[], int T, int Y[]) {
for (int i = 0; i < S; i++) {
update(X[i], false);
}
ll ans = INF;
for (int i = 0; i < T; i++) {
setmin(ans, query(Y[i]));
}
for (int i = 0; i < S; i++) {
update(X[i], true);
}
return ans;
}
