#include "deliveries.h"
#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
//#define int long long
#define ll long long
#define ull unsigned long long
#define down cout<<'\n';
#define debug cout<<" cucuucucuuu",down
#define modwwe int t;cin>>t; while(t--)
#define bit(i,j) (i>>j&1)
#define sobit(a) __builtin_popcountll(a)
#define task2 "top1apio"
#define task "test"
#define fin(x) freopen(x".inp","r",stdin)
#define fou(x) freopen(x".out","w",stdout)
#define pb push_back
#define mask(k) (1ll<<k)
#define checktime cerr << (double)clock() / CLOCKS_PER_SEC * 1000 << " ms";
using namespace std;
#define getchar_unlocked getchar
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
using i128 = __int128;
int rand(int l, int r)
{
return uniform_int_distribution<int>(l, r)(rd);
}
void phongbeo();
const int inf = 1e17+7;
const int mod2 = 1e9+7;
//const ll base=67;
ll n, m, s1, s2, s4, s3, sf, k, s5, s6, s7, s8, s9, mx2, res, dem2 = 0, dem = 0, s33, dem3, dem4, mid, l2,
r2, center;
ll i, s10, s12, k1, k2, k3, s11, lim, w, l, r, dem5, dem6, dem7, dem9, root, en;
ll el = 19;
struct ib{ll a,b;};
vector<ib> v[100001];
ll heavy[100001];
ll head[100001];
ll par[100001];
ll dist[100001];
ll in[100001],g[100001],ou[100001],num[100001];
ll dfs(ll x,ll y)
{
ll sz=1,mxz=0;
for(auto [f,cost]:v[x])
if(f^y)
{
dist[f]=dist[x]+cost;
par[f]=x;
ll s=dfs(f,x);
sz+=s;
if(s>mxz)mxz=s,heavy[x]=f;
}
return sz;
}
void des(ll x,ll y)
{
head[x]=y;
in[x]=++dem;
g[dem]=x;
if(heavy[x]!=0)
{
des(heavy[x],y);
for(auto [f,cost]:v[x])
if(!in[f])
des(f,f);
}
ou[x]=dem;
}
struct segtree
{
ll t[400001],lazy[400001];
void apply(ll node,ll x)
{
t[node]+=x;
lazy[node]+=x;
}
void ff(ll x)
{
for(ll i=x*2;i<=x*2+1;i++)
apply(i,lazy[x]);
lazy[x]=0;
}
void upd(ll node,ll l,ll r,ll l1,ll r1,ll x)
{
if(l>r1||r<l1)return;
if(l>=l1&&r<=r1)
{
apply(node,x);
return;
}
ll mid=l+r>>1;
if(lazy[node]!=0)ff(node);
upd(node<<1,l,mid,l1,r1,x);
upd(node<<1|1,mid+1,r,l1,r1,x);
t[node]=max(t[node<<1],t[node<<1|1]);
}
ll get(ll node,ll l,ll r,ll x)
{
if(l==r){
return g[l];
}
if(lazy[node]!=0)ff(node);
ll mid=l+r>>1;
if(t[node<<1|1]*2>=x)return get(node<<1|1,mid+1,r,x);
return get(node<<1,l,mid,x);
}
} st;
struct fenwicktree
{
ll bit[100001];
void upd(ll x,ll y)
{
for(x; x<=n; x+=x&-x)
bit[x]+=y;
}
ll get(ll x)
{
ll s=0;
for(x; x; x-=x&-x)
s+=bit[x];
return s;
}
} fen,fen2,fen3;
void buff(ll x,ll y,ll z)
{
fen.upd(in[x],y*z-dist[x]*z*2);
st.upd(1,1,n,in[head[x]],in[x],z);
if(head[x]!=0)buff(par[head[x]],y,z);
}
void init(int N,vector<int> U,vector<int> V,vector<int> T,vector<int> W)
{
n=N;
for(int i=0; i<n-1; i++)
v[U[i]].pb({V[i],T[i]}),
v[V[i]].pb({U[i],T[i]});
for(int i=0; i<n; i++)
num[i]=W[i];
num[0]++;
dfs(0,-1);
des(0,0);
for(int i=0; i<n; i++)
if(num[i]!=0)
{
buff(i,dist[i],num[i]);
fen2.upd(in[i],num[i]*dist[i]);
fen3.upd(in[i],num[i]);
}
}
ll gg(ll x,ll y,ll z)
{
return fen2.get(y)-fen2.get(x)-(fen3.get(y)-fen3.get(x))*z*2;
}
ll hihi(ll x,ll y)
{
return fen.get(x)-fen.get(y);
}
ll max_time(int x,int y)
{
if(x==0)y++;
buff(x,dist[x],y-num[x]);
fen2.upd(in[x],(y-num[x])*dist[x]);
fen3.upd(in[x],y-num[x]);
num[x]=y;
ll center=st.get(1,1,n,st.t[1]);
s4=dist[center]*st.t[1];
ll lastl=0,lastr=0;
while(true)
{
s4+=gg(in[center]-1,ou[center],dist[center])-gg(lastl,lastr,dist[center]);
if(head[center]==0)s4+=fen.get(in[par[center]]);
else s4+=hihi(in[par[center]],in[par[head[center]]]);
center=head[center];
lastl=in[center]-1;
lastr=ou[center];
if(center==0)break;
center=par[center];
}
return s4*2;
}
