#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1e17;
struct ST {
int n;
vector<ll> t;
ST() {}
ST(int n): n(n) { t.assign(2*n, INF); }
void update(int i, ll v) {
for(t[i += n] = v; i > 1; i >>= 1) t[i>>1] = min(t[i], t[i^1]);
}
ll query(int l, int r) {
ll res = INF;
for(l += n, r += n+1; l < r; l >>= 1, r >>= 1) {
if(l & 1) res = min(t[l++], res);
if(r & 1) res = min(t[--r], res);
}
return res;
}
} stup, stdown;
int n;
vector<vector<pair<int,int> > > g;
vector<int> sz, in, out, rev, par, nxt, pre;
vector<ll> d;
void dfs_sz(int u = 0) {
sz[u] = 1;
if(g[u].front().first == par[u]) swap(g[u].front(), g[u].back());
for(auto &p: g[u]) {
int v, w; tie(v, w) = p;
if(v == par[u]) continue;
d[v] = d[u] + w;
par[v] = u;
dfs_sz(v);
sz[u] += sz[v];
if(sz[v] > sz[g[u].front().first]) swap(p, g[u].front());
}
}
void dfs_hld(int u = 0) {
static int curr_t = 0;
in[u] = curr_t++;
rev[in[u]] = u;
pre[u] = u;
for(auto p: g[u]) {
int v, w; tie(v, w) = p;
if(v == par[u]) continue;
nxt[v] = (v == g[u].front().first ? nxt[u] : v);
dfs_hld(v);
if(v == g[u].front().first) pre[u] = pre[v];
}
out[u] = curr_t - 1;
// cout << u << ' ' << d[u] << ' ' << pre[u] << ' ' << nxt[u] << endl;
}
void Init(int N, int A[], int B[], int D[]) {
n = N;
g.resize(n);
sz.resize(n), in.resize(n), out.resize(n), rev.resize(n), par.resize(n), nxt.resize(n), pre.resize(n);
d.resize(n);
stup = ST(n), stdown = ST(n);
for(int i = 0; i < n-1; i++) {
g[A[i]].emplace_back(B[i], D[i]);
g[B[i]].emplace_back(A[i], D[i]);
}
par[0] = -1;
dfs_sz();
dfs_hld();
}
ll Query(int S, int X[], int T, int Y[]) {
ll ret = INF;
for(int i = 0; i < S; i++) {
stdown.update(in[X[i]], d[X[i]]);
for(int v = X[i]; v != -1; v = par[nxt[v]]) {
// cout << X[i] << ' ' << v << ' ' << d[X[i]] + d[pre[v]] - 2*d[v] << endl;
stup.update(in[v], min(stup.query(in[v], in[v]), d[X[i]] - 2*d[v]));
}
}
for(int i = 0; i < T; i++) {
ret = min(stdown.query(in[Y[i]], out[Y[i]]) - d[Y[i]], ret);
// cout << Y[i] << ' ' << stdown.query(in[Y[i]], out[Y[i]]-1) << endl;
for(int v = Y[i]; v != -1; v = par[nxt[v]]) {
ret = min(stup.query(in[nxt[v]], in[v]) + d[Y[i]], ret);
}
}
for(int i = 0; i < S; i++) {
stdown.update(in[X[i]], INF);
for(int v = X[i]; v != -1; v = par[nxt[v]]) {
stup.update(in[v], INF);
}
}
return ret;
}
