#include <bits/stdc++.h>
#define ll long long
#include "factories.h"
using namespace std;
constexpr ll INF = 1e18;
int n;
vector<vector<pair<int, ll>>> adj;
vector<int> visited;
vector<int> sz;
vector<int> parent;
vector<int> enter;
vector<ll> dist;
vector<int> order;
vector<int> depth;
vector<int> to_del;
vector<ll> closest;
vector<array<pair<int, int>, 20>> sp;
int ind = 0;
int get_sz(int node, int par)
{
sz[node] = 1;
for (auto i : adj[node])
{
if (visited[i.first] || i.first == par) continue;
sz[node] += get_sz(i.first, node);
}
return sz[node];
}
int get_centroid(int node, int par, int sub_sz)
{
for (auto i : adj[node])
{
if (visited[i.first] || i.first == par) continue;
if (sz[i.first] * 2 > sub_sz) return get_centroid(i.first, node, sub_sz);
}
return node;
}
void get_centroid_decomp(int node, int prv)
{
int centroid = get_centroid(node, -1, get_sz(node, -1));
visited[centroid] = ++ind;
parent[centroid] = prv;
for (auto i : adj[centroid])
{
if (visited[i.first]) continue;
get_centroid_decomp(i.first, centroid);
}
}
void dfs(int node, int par, ll d, int dep)
{
enter[node] = (int)order.size();
order.emplace_back(node);
dist[node] = d;
depth[node] = dep;
for (auto i : adj[node])
{
if (i.first == par) continue;
dfs(i.first, node, d + i.second, dep + 1);
order.emplace_back(node);
}
}
void get_sp()
{
for (int i = 0; i < n * 2 - 1; i++) sp[i][0] = make_pair(depth[order[i]], order[i]);
for (int i = 1; i < 20; i++)
{
for (int j = 0; j + (1 << i) <= n * 2 - 1; j++)
sp[j][i] = min(sp[j][i - 1], sp[j + (1 << (i - 1))][i - 1]);
}
}
ll get_dist(int a, int b)
{
int oa = order[a], ob = order[b];
if (oa > ob) swap(oa, ob);
int len = __lg(ob - oa + 1);
auto i = min(sp[oa][len], sp[ob - (1 << len) + 1][len]);
return dist[a] + dist[b] - dist[i.second] * 2;
}
void modify(int node)
{
int temp = node;
for (; node != -1; node = parent[node])
{
ll zw = get_dist(node, temp);
if (zw < closest[node])
{
closest[node] = zw;
to_del.emplace_back(node);
}
}
}
ll ask(int node)
{
ll ans = INF;
int temp = node;
for (; node != -1; node = parent[node])
{
ans = min(ans, get_dist(temp, node) + closest[node]);
}
return ans;
}
void Init(int N, int A[], int B[], int D[])
{
n = N;
adj.resize(n);
visited.resize(n);
parent.resize(n);
sz.resize(n);
enter.resize(n);
dist.resize(n);
depth.resize(n);
closest.resize(n, INF);
sp.resize(n * 2 - 1);
for (int i = 0; i < N - 1; i++)
{
adj[A[i]].emplace_back(B[i], D[i]);
adj[B[i]].emplace_back(A[i], D[i]);
}
get_centroid_decomp(0, -1);
dfs(0, -1, 0, 0);
get_sp();
}
long long Query(int S, int X[], int T, int Y[])
{
for (int i = 0; i < S; i++)
{
modify(X[i]);
}
ll ans = INF;
for (int i = 0; i < T; i++) ans = min(ans, ask(i));
for (auto i : to_del) closest[i] = INF;
return ans;
}
