#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
#define f first
#define s second
vector <pi> adjlist[500005];
int sub[500005], lvl[500005], p[500005];
ll dist[500005][19], ans[500005];
stack <int> st;
ll INF = 1e18;
int subtrsz(int x, int par, int l) {
sub[x] = 1;
//subtree size is 1
for (auto it:adjlist[x]) {
if (lvl[it.f] != -1) continue;
// already added to centroid tree
if (it.f == par) continue;
if (l) dist[it.f][l-1] = dist[x][l-1] + it.s;
sub[x] += subtrsz(it.f, x, l);
}
return sub[x];
}
int findcent(int x, int par, int n) {
//n is size of subtree
for (auto it:adjlist[x]) {
if (lvl[it.f] != -1) continue;
// Already added to centroid tree
if (it.f != par and sub[it.f] > n/2) {
return findcent(it.f, x, n);
}
}
return x; // No subtree has size > n/2
// so you are the centroid
}
//building from node x, with parent par, level l
void build(int x, int par, int l) {
int n = subtrsz(x, par, l);
int cent = findcent(x, par, n);
// find centroid with the subtree size
if (par == -1) par = cent; //par of root is itself
p[cent] = par; //set parent of centroid
// to be the previous centroid
lvl[cent] = l;
for (auto it:adjlist[cent]) {
if (lvl[it.f] != -1) continue;
// already added to centroid tree
dist[it.f][l] = it.s;
// distance from this node to the centroid at level l
build(it.f, cent, l+1);
}
}
void update(int x) {
int l = lvl[x];
int y = x;
while (l != -1) {
ans[y] = min(ans[y], dist[x][l]);
//ans[y] = min distance from any node
//of Factory A to y.
//here we process by x
st.push(y);
y = p[y];
l--;
}
}
ll findans(int x) {
ll ret = INF;
int l = lvl[x];
int y = x;
while (l != -1) {
ret = min(ret, ans[y] + dist[x][l]);
//for every centroid, add dist from
//best Factory A node to querying Factory B node
//then min with running answer
y = p[y];
l--;
}
return ret;
}
void Init(int N, int A[], int B[], int D[]) {
for (int i = 0; i < N-1; i++) {
adjlist[A[i]].push_back(pi(B[i], D[i]));
adjlist[B[i]].push_back(pi(A[i], D[i]));
}
memset(lvl, -1, sizeof lvl);
build(0, -1, 0); //build centroid tree
for (int i = 0; i < N; i++) ans[i] = INF;
//for (int i=0;i<N;++i)cout<<p[i]<<' '<<lvl[i]<<' '<<dist[i][0]<<'\n';cout<<'\n';
}
long long Query(int S, int X[], int T, int Y[]) {
for (int i = 0; i < S; i++) update(X[i]);
//find min dist from every node to Factory A nodes
ll ret = INF;
for (int i = 0; i < T; i++) ret = min(ret, findans(Y[i]));
//find min dist from every node to Factory B nodes
while (st.size()) {
ans[st.top()] = INF;
st.pop();
}
return ret;
}
