#ifndef FACTORIES_H_
#define FACTORIES_H_
#include <bits/stdc++.h>
//#include "bits_stdc++.h"
#define f first
#define s second
#define mp make_pair
#define pb push_back
#define lb lower_bound
#define ub upper_bound
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pi;
ll const MAXN = 500005;
ll sub[MAXN], lvl[MAXN], par[MAXN], m[MAXN], dist[MAXN];
vector<pi> V[MAXN];
ll twok[MAXN][25];
ll depth[MAXN];
ll n;
// 2k decomposition
void dfs(ll p, ll node)
{
for (pi u: V[node])
{
if (p==u.f) continue;
dist[u.f] = dist[node] + u.s;
twok[u.f][0] = node;
depth[u.f] = depth[node]+1;
dfs(node, u.f);
}
}
ll kpar(ll x, ll k)
{
for (ll i=0; i<20; ++i)
{
if (k& (1<<i))
{
x=twok[x][i];
}
}
return x;
}
ll lca(ll a, ll b)
{
if (depth[a]<depth[b]) swap(a,b);
a = kpar(a, depth[a]-depth[b]);
if (a==b) return a;
for (ll k=19; k>=0; k--)
{
if (twok[a][k]!=twok[b][k])
{
a=twok[a][k]; b = twok[b][k];
}
}
return twok[a][0];
}
ll sp(ll a, ll b)
{
return dist[a]+dist[b]-2*dist[lca(a,b)];
}
// centroid decomposition
ll dfs1(int u, int p, int l) {
sub[u] = 1; // Subtree size is 1
for (pi v : V[u]) {
if (lvl[v.f] != -1) continue; // Already added to centroid tree
if (v.f == p) continue;
sub[u] += dfs1(v.f, u, l); // Increase size of subtree
}
return sub[u];
}
ll dfs2(int u, int p, int n) { // Pass in the size of the subtree
for (pi v : V[u]) {
if (lvl[v.f] != -1) continue; // Already added to centroid tree
if (v.f != p && sub[v.f] > n / 2) {
return dfs2(v.f, u, n); // DFS to that node
}
}
return u; // No child has size more than n/2, hence you are the centroid
}
// Building from node u, with a parent p and level l
void build(int u, int p, int l) {
int n = dfs1(u, p, l); // Find the size of each subtree
int cent = dfs2(u, p, n); // Find the centroid
if (p == -1) p = cent; // Parent of root is yourself
par[cent] = p; // Set the parent of centroid to the previous centroid
lvl[cent] = l;
for (pi v : V[cent]) {
if (lvl[v.f] != -1) continue;
// If we have already added to centroid then we ignore
build(v.f, cent, l + 1); // Recursively build each subtree
}
}
//To construct the centroid tree, call build(root, -1, 0);
void Init(int N, int A[], int B[], int D[])
{
n=N;
for (ll i=0; i<n-1; ++i)
{
V[A[i]].pb(mp(B[i], D[i]));
V[B[i]].pb(mp(A[i], D[i]));
}
dist[0]=0;
depth[0] = 0;
twok[0][0] = -1;
dfs(-1,0);
for (ll k=1; k<20; k++)
{
for (ll x=0; x<n; ++x)
{
if (twok[x][k-1]==-1) continue;
twok[x][k] = twok[twok[x][k-1]][k-1];
}
}
memset(lvl, -1, sizeof lvl);
build(0, -1, 0);
for (ll i=0; i<=n-1; ++i) {m[i]=LLONG_MAX;} // < n not <n-1
}
long long Query(int S, int X[], int T, int Y[])
{
for (ll i=0; i<S; ++i)
{
ll nxt = X[i];
m[nxt] = 0;
while (par[nxt]!=nxt)
{
nxt = par[nxt];
m[nxt] = min(m[nxt], sp(nxt, X[i]));
//cout << "sp is " << sp(nxt, X[i]) << endl;
//cout << "nxt become " << m[nxt] << endl;
}
}
ll ans = LLONG_MAX;
for (ll i=0; i<T; ++i)
{
//cout << i << endl;
ll nxt = Y[i];
//cout << " nxt is " << nxt << endl;
ans = min(ans, m[nxt]); // dont declare ans again
//cout << "ans become " << ans << endl;
while (par[nxt]!=nxt)
{
nxt = par[nxt];
//cout << " go to " << nxt << endl;
if (m[nxt]!=LLONG_MAX) {ans = min(ans, m[nxt] + sp(nxt, Y[i]));}
//cout << "sp is " << sp(nxt, Y[i]) << endl;
//cout << "ans become " << ans << endl;
}
}
for (ll i=0; i<S; ++i)
{
ll nxt = X[i];
m[nxt] = LLONG_MAX;
while (par[nxt]!=nxt) {nxt = par[nxt]; m[nxt]=LLONG_MAX;}
}
//cout << "final ans is " << endl;
return ans;
}
#endif /* FACTORIES_H_ */
