#include<bits/stdc++.h>
#include "deliveries.h"
using namespace std;
struct Edge
{
int b,c;
};
vector<Edge>D[100009];
int Deliv[100009];
long long NadMna[100009];
long long NadSuma[100009];
long long Suma[100009];
bool CzyGit[100009];
int n;
void DFS(int v, int last)
{
NadMna[v]=Deliv[v];
NadSuma[v]=0;
for(auto[som,o] : D[v])
{
if(som==last){continue;}
DFS(som,v);
NadMna[v]+=NadMna[som];
NadSuma[v]+=NadMna[som]*o+NadSuma[som];
}
}
void DFS2(int v, int last)
{
long long maxx=0;
for(auto[som,o] : D[v])
{
if(som==last){continue;}
Suma[som]=Suma[v]+(NadMna[0]-NadMna[som])*o-NadMna[som]*o;
maxx=max(maxx,NadMna[som]);
DFS2(som,v);
}
maxx=max(maxx,NadMna[0]-NadMna[v]);
int odj=0;
if(v==0){odj=1;}
if(maxx*2>NadMna[0]-odj){CzyGit[v]=0;}
else{CzyGit[v]=1;}
}
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++)
{
int a=AA[i];
int b=BB[i];
int c=CC[i];
D[a].push_back({b,c});
D[b].push_back({a,c});
}
for(int i=0;i<n;i++)
{
Deliv[i]=W[i];
}
Deliv[0]++;
return;
}
long long max_time(int v, int x)
{
if(v==0){x++;}
Deliv[v]=x;
DFS(0,-1);
Suma[0]=NadSuma[0];
DFS2(0,-1);
long long wyn=0;
for(int i=0;i<n;i++)
{
if(CzyGit[i]==0){continue;}
wyn=max(wyn,Suma[i]*2);
}
return wyn;
}
