#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define _CRT_SECURE_NO_WARNINGS
#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, par, nxt, pre;
vector<ll> d;
void dfs_sz(int u = 0) {
sz[u] = 1;
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];
}
for(auto &p: g[u])
if(g[u].front().first == par[u] || sz[p.first] > 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++;
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] << ' ' << 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), 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++) {
for(int v = X[i]; v != -1; v = par[nxt[v]]) {
stup.update(in[v], min(stup.t[n+in[v]], d[X[i]] - (d[v] << 1)));
stdown.update(in[v], min(stdown.t[n+in[v]], d[X[i]]));
}
}
for(int i = 0; i < T; i++) {
ll tmp = INF;
for(int v = Y[i]; v != -1; v = par[nxt[v]]) {
tmp = min(stup.query(in[nxt[v]], in[v]), tmp);
tmp = min(stdown.query(in[v], in[pre[v]]) - (d[v] << 1), tmp);
}
ret = min(tmp + d[Y[i]], ret);
}
for(int i = 0; i < S; i++) {
for(int v = X[i]; v != -1; v = par[nxt[v]]) {
stup.update(in[v], INF);
stdown.update(in[v], INF);
}
}
return ret;
}
