#include<bits/stdc++.h>
#include "deliveries.h"
using namespace std;
struct Edge
{
int som,o;
};
vector<Edge>D[200009];
vector<int>G[200009],Skad[200009];
bool zaj[200009];
long long Suma[200009],Ile[200009];
vector<long long>Suma2[200009],Ile2[200009];
long long Odl[20][200009];
int NadMna[200009],Deep[200009],Last[200009],Numer[200009];
int tab[200009];
int Gl[200009],Gp[200009],GLast[200009];
long long Tre[1000000];
int n,centr,base,start,h;
long long s=0;
long long Przedzial(int l, int p)
{
l+=base;
p+=base;
long long wyn=0;
while(l<=p)
{
if(l%2==1)
{
wyn+=Tre[l];
l++;
}
if(p%2==0)
{
wyn+=Tre[p];
p--;
}
l>>=1;
p>>=1;
}
return wyn;
}
void Punkt(int v, int dod)
{
v+=base;
while(v>0)
{
Tre[v]+=dod;
v>>=1;
}
}
int TworzenieDrzewa(int x)
{
x--;
int u=1;
while(x>0)
{
x>>=1;
u<<=1;
}
return u;
}
long long IleNad(int a, int b)
{
if(b==GLast[a])
{
return s-Przedzial(Gl[a],Gp[a]);
}
else
{
return Przedzial(Gl[b],Gp[b]);
}
}
void GDFS(int v, int last)
{
GLast[v]=last;
for(auto[som,o] : D[v])
{
if(som==last){continue;}
GDFS(som,v);
}
Gl[v]=h;
Gp[v]=h;
h--;
for(auto[som,o] : D[v])
{
if(som==last){continue;}
Gp[v]=max(Gp[v],Gp[som]);
}
}
void CentrDod(int v, int dod)
{
Punkt(Gl[v],dod);
s+=dod;
Ile[v]+=dod;
int u=v;
while(Last[u]!=-1)
{
int num=Numer[u];
u=Last[u];
Suma[u]+=Odl[Deep[u]][v]*dod;
Ile[u]+=dod;
Suma2[u][num]+=Odl[Deep[u]][v]*dod;
Ile2[u][num]+=dod;
}
}
long long CentrOblicz(int v)
{
long long wynik=Suma[v];
int u=v;
while(Last[u]!=-1)
{
int num=Numer[u];
u=Last[u];
wynik+=Suma[u]-Suma2[u][num];
wynik+=(Ile[u]-Ile2[u][num])*Odl[Deep[u]][v];
}
return wynik;
}
void DFSCentr(int v, int last,const int &r)
{
NadMna[v]=1;
bool cv=1;
for(auto[som,o] : D[v])
{
if(som==last||zaj[som]){continue;}
DFSCentr(som,v,r);
NadMna[v]+=NadMna[som];
if(NadMna[som]>(r>>1)){cv=0;}
}
if(r-NadMna[v]>(r>>1)){cv=0;}
if(cv){centr=v;}
}
void DFSOdl(int v, int deep, long long odl, int last)
{
Odl[deep][v]=odl;
for(auto[som,o] : D[v])
{
if(som==last||zaj[som]){continue;}
DFSOdl(som,deep,odl+o,v);
}
}
void CENTROID(int v, int r, int deep, int last, int numer)
{
DFSCentr(v,-1,r);
if(last!=-1)
{
G[last].push_back(centr);
Skad[last].push_back(v);
}
v=centr;
Deep[v]=deep;
Last[v]=last;
Numer[v]=numer;
Suma2[v].resize(D[v].size());
Ile2[v].resize(D[v].size());
DFSOdl(v,deep,0,-1);
DFSCentr(v,-1,0);
zaj[v]=1;
for(int i=0;i<(int)D[v].size();i++)
{
const int som=D[v][i].som;
if(zaj[som]){continue;}
CENTROID(som,NadMna[som],deep+1,v,i);
}
zaj[v]=0;
}
void F(int v, vector<Edge>U)
{
if(U.size()==0){return;}
if(U.size()<=2)
{
for(Edge e : U)
{
D[v].push_back(e);
D[e.som].push_back({v,e.o});
}
return;
}
vector<Edge>A,B;
while(U.size()>0)
{
if(A.size()<=B.size()){A.push_back(U.back());}
else{B.push_back(U.back());}
U.pop_back();
}
n++;
const int u=n-1;
D[v].push_back({u,0});
D[u].push_back({v,0});
F(u,A);
F(u,B);
}
void DFS(int v, int last)
{
vector<Edge>U;
for(int i=0;i<(int)D[v].size();i++)
{
const int som=D[v][i].som;
if(som==last){continue;}
U.push_back(D[v][i]);
DFS(som,v);
}
D[v].clear();
F(v,U);
}
long long GetWynik()
{
int v=start;
while(true)
{
pair<int,int>maxx={0,0};
for(int i=0;i<(int)G[v].size();i++)
{
maxx=max(maxx,{IleNad(v,Skad[v][i]),G[v][i]});
}
if(maxx.first>(s>>1)){v=maxx.second;}
else
{
return CentrOblicz(v)*2;
}
}
}
void init(int N, vector<int>AA, vector<int>BB, vector<int>CC, vector<int>W)
{
n=N;
for(int i=0;i<n-1;i++)
{
D[AA[i]].push_back({BB[i],CC[i]});
D[BB[i]].push_back({AA[i],CC[i]});
}
DFS(0,-1);
base=TworzenieDrzewa(n);
h=n;
GDFS(0,-1);
CENTROID(0,n,0,-1,-1);
for(int i=0;i<n;i++)
{
if(Deep[i]==0)
{
start=i;
break;
}
}
W[0]++;
for(int i=0;i<(int)W.size();i++)
{
CentrDod(i,W[i]);
tab[i]=W[i];
}
}
long long max_time(int v, int x)
{
if(v==0){x++;}
int dod=x-tab[v];
tab[v]=x;
CentrDod(v,dod);
return GetWynik();
}
