#include <bits/stdc++.h>
#include "factories.h"
using namespace std;
#define pb push_back
#define ll long long int
#define ff first
#define ss second
const ll INF = 1000000000000000000;
vector<int> adj[1000010];
vector<int> weight[1000010];
bool removed[1000010];
int sub[1000010];
int paiCentroid[1000010];
pair<ll, int> minFactoryDist[1000010];
int ancestor[1000010][30];
ll nivel[1000010];
int tin[1000010], tout[1000010];
int h = 0;
int tempo = 0;
int curQuery = 0;
void dfsInit(int cur, int pai){
sub[cur] = 1;
for(int i=0;i<(int)adj[cur].size();i++){
int viz = adj[cur][i];
if(removed[viz]) continue;
if(viz==pai) continue;
dfsInit(viz, cur);
sub[cur] += sub[viz];
}
}
int findCentroid(int cur, int pai, int size){
for(int i=0;i<(int)adj[cur].size();i++){
int viz = adj[cur][i];
if(removed[viz]) continue;
if(viz==pai) continue;
if(sub[viz]>size/2) return findCentroid(viz, cur, size);
}
return cur;
}
void createCentroidTree(int cur, int centroidPai){
dfsInit(cur, cur);
int centroid = findCentroid(cur, cur, sub[cur]);
paiCentroid[centroid] = centroidPai;
removed[centroid] = true;
for(int i=0;i<(int)adj[centroid].size();i++){
int viz = adj[centroid][i];
if(removed[viz]) continue;
createCentroidTree(viz, centroid);
}
}
void dfs(int cur, int pai){
tempo++;
tin[cur] = tempo;
ancestor[cur][0] = pai;
for(int i=1;i<=h;i++) ancestor[cur][i] = ancestor[ancestor[cur][i-1]][i-1];
for(int i=0;i<(int)adj[cur].size();i++){
int viz = adj[cur][i];
int w = weight[cur][i];
if(viz==pai) continue;
nivel[viz] = nivel[cur] + w;
dfs(viz, cur);
}
tout[cur] = tempo;
}
bool isAncestor(int a, int b){
return tin[a]<=tin[b] && tout[b]<=tout[a];
}
int lca(int a, int b){
if(isAncestor(a, b)) return a;
if(isAncestor(b, a)) return b;
for(int i=h;i>=0;i--) if(!isAncestor(ancestor[a][i], b)) a = ancestor[a][i];
return ancestor[a][0];
}
ll calculaDist(int a, int b){
int lca_ = lca(a, b);
ll resp = abs(nivel[lca_] - nivel[a]) + abs(nivel[lca_] - nivel[b]);
return resp;
}
void update(int v){
int cur = v;
while(cur!=-1){
ll distancia = calculaDist(v, cur);
if(minFactoryDist[cur].ss<curQuery){
minFactoryDist[cur].ff = distancia;
minFactoryDist[cur].ss = curQuery;
}else{
minFactoryDist[cur].ff = min(minFactoryDist[cur].ff, distancia);
}
cur = paiCentroid[cur];
}
}
ll calculaMinFactoryDist(int v){
int cur = v;
ll resp = INF;
while(cur!=-1){
ll distancia = calculaDist(v, cur);
if(minFactoryDist[cur].ss==curQuery) resp = min(resp, distancia + minFactoryDist[cur].ff);
cur = paiCentroid[cur];
}
return resp;
}
void Init(int N, int A[], int B[], int D[]){
for(int i=0;i<N-1;i++){
int a = A[i], b = B[i], d = D[i];
adj[a].pb(b);
weight[a].pb(d);
adj[b].pb(a);
weight[b].pb(d);
}
nivel[0] = 0;
h = ceil(log2(N));
dfs(0, 0);
createCentroidTree(0, -1);
}
long long Query(int S, int X[], int T, int Y[]){
curQuery++;
for(int i=0;i<S;i++) update(X[i]);
//for(int i=0;i<7;i++) printf("%d %d %d %d\n", i, nivel[i], minFactoryDist[i].ff, minFactoryDist[i].ss);
ll resp = INF;
for(int i=0;i<T;i++) resp = min(resp, calculaMinFactoryDist(Y[i]));
return resp;
}
/*int main()
{
int n, q; scanf("%d %d", &n, &q);
int a[100010], b[100010], d[100010];
for(int i=0;i<n-1;i++) scanf("%d %d %d", &a[i], &b[i], &d[i]);
Init(n, a, b, d);
for(int i=0;i<q;i++){
int s, t; scanf("%d %d", &s, &t);
int x[10010], y[10010];
for(int j=0;j<s;j++) scanf("%d", &x[j]);
for(int j=0;j<t;j++) scanf("%d", &y[j]);
printf("%lld\n", Query(s, x, t, y));
}
return 0;
}*/
