#include <bits/stdc++.h>
#include "deliveries.h"
using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
const ll I = 1000LL * 1000LL * 1000LL * 1000LL * 1000LL * 1000LL;
const int II = 2 * 1000 * 1000 * 1000;
const ll M = 1000LL * 1000LL * 1000LL + 7LL;
const int N = 1<<17;
int n;
ll tab[N], sum[N], pth[N];
ll al = 0LL;
vector<pair<int, ll>> ed[N];
bool vis[N];
int cnt = 0, clrcnt = 0;
int pos[N], revp[N], frs[N], sp[N], oj[N], il[N];
ll drzs[2 * N], dod[2 * N], l1[2 * N];
ll drzc[2 * N], l2[2 * N];
inline void PushC(int v)
{
drzc[v * 2] += l2[v]; l2[v * 2] += l2[v];
drzc[v * 2 + 1] += l2[v]; l2[v * 2 + 1] += l2[v];
l2[v] = 0;
}
void AddC(int v, int p, int k, int pz, int kz, ll x)
{
if(p > kz || k < pz) return;
if(p >= pz && k <= kz)
{
drzc[v] += x; l2[v] += x;
return;
}
AddC(v * 2, p, (p + k) / 2, pz, kz, x);
AddC(v * 2 + 1, (p + k) / 2 + 1, k, pz, kz, x);
drzc[v] = max(drzc[v * 2], drzc[v * 2 + 1]) + l2[v];
}
int FindC(ll x)
{
int v = 1;
while(v < N)
{
PushC(v);
v *= 2; ++v;
if(drzc[v] < x) --v;
}
return v - N;
}
inline void PushS(int v)
{
drzs[v * 2] += dod[v * 2] * l1[v]; l1[v * 2] += l1[v];
drzs[v * 2 + 1] += dod[v * 2 + 1] * l1[v]; l1[v * 2 + 1] += l1[v];
l1[v] = 0LL;
}
void AddS(int v, int p, int k, int pz, int kz, ll x)
{
if(p > kz || k < pz) return;
if(p >= pz && k <= kz)
{
drzs[v] += dod[v] * x; l1[v] += x;
return;
}
PushS(v);
AddS(v * 2, p, (p + k) / 2, pz, kz, x);
AddS(v * 2 + 1, (p + k) / 2 + 1, k, pz, kz, x);
drzs[v] = drzs[v * 2] + drzs[v * 2 + 1];
}
ll QueryS(int v, int p, int k, int pz, int kz)
{
if(p > kz || k < pz) return 0LL;
if(p >= pz && k <= kz)
return drzs[v];
ll ans;
PushS(v);
ans = QueryS(v * 2, p, (p + k) / 2, pz, kz);
ans += QueryS(v * 2 + 1, (p + k) / 2 + 1, k, pz, kz);
return ans;
}
void DFS(int v)
{
vis[v] = true;
sum[v] = tab[v]; il[v] = 1;
for(int i = 0; i < (int)ed[v].size(); ++i)
{
if(vis[ed[v][i].st]) continue;
pth[ed[v][i].st] = pth[v] + ed[v][i].nd;
oj[ed[v][i].st] = v;
DFS(ed[v][i].st);
sum[v] += sum[ed[v][i].st];
il[v] += il[ed[v][i].st];
}
//cerr << answer << " dfs: " << v - 1 << " " << sum[v] << " " << al << " " << ev << "\n";
vis[v] = false;
}
void DFSH(int v, int clr, ll ev)
{
drzs[pos[v] + N] = ev * sum[v];
dod[pos[v] + N] = ev;
drzc[pos[v] + N] = sum[v];
//cerr << "HLD " << v << " " << clr << " " << pos[v] << " " << ev << " " << sum[v] << "\n";
revp[pos[v]] = v;
pair<int, int> ma = make_pair(-1, -1);
sp[v] = clr;
for(int i = 0; i < (int)ed[v].size(); ++i)
if(sp[ed[v][i].st] == 0)
ma = max(ma, make_pair(il[ed[v][i].st], i));
if(ma == make_pair(-1, -1)) return;
int ne = ed[v][ma.nd].st;
pos[ne] = pos[v] + 1; ++cnt;
DFSH(ne, clr, ed[v][ma.nd].nd);
for(int i = 0; i < (int)ed[v].size(); ++i)
{
int ne = ed[v][i].st;
if(sp[ne]) continue;
++clrcnt;
++cnt; pos[ne] = cnt;
frs[clrcnt] = ne;
DFSH(ne, clrcnt, ed[v][i].nd);
}
}
void HLDChange(int v, ll x)
{
while(v > 0)
{
int a = pos[frs[sp[v]]], b = pos[v];
AddC(1, 0, N - 1, a, b, x);
AddS(1, 0, N - 1, a, b, x);
v = oj[frs[sp[v]]];
}
}
ll HLDQuery(int v)
{
ll s = 0LL;
while(v > 0)
{
int a = pos[frs[sp[v]]], b = pos[v];
s += QueryS(1, 0, N - 1, a, b);
v = oj[frs[sp[v]]];
}
return s;
}
void InitTrees()
{
for(int v = N - 1; v >= 1; --v)
{
drzc[v] = max(drzc[v * 2], drzc[v * 2 + 1]);
drzs[v] = drzs[v * 2] + drzs[v * 2 + 1];
dod[v] = dod[v * 2] + dod[v * 2 + 1];
}
}
void init(int _N, vector<int> U, vector<int> V, vector<int> T, vector<int> W)
{
n = _N;
for(int i = 1; i <= n; ++i) tab[i] = W[i - 1];
tab[1] += 1LL;
for(int i = 1; i <= n; ++i) al += tab[i];
for(int i = 0; i < n - 1; ++i)
{
ed[U[i] + 1].pb(make_pair(V[i] + 1, (ll)T[i]));
ed[V[i] + 1].pb(make_pair(U[i] + 1, (ll)T[i]));
}
oj[1] = 1;
DFS(1);
cnt = 1; clrcnt = 1;
pos[1] = 1; frs[1] = 1;
DFSH(1, 1, 0LL);
oj[1] = 0;
InitTrees();
//cerr << "After Init " << drzs[1] << "\n";
}
long long max_time(int S, int X)
{
++S; if(S == 1) ++X;
ll ch = X - tab[S];
tab[S] += ch; al += ch;
HLDChange(S, ch);
ll answer = drzs[1];
//cout << "Beg " << answer << "\n";
int cen = revp[FindC((al + 1LL) / 2LL)];
//cout << "centroid " << cen << "\n";
answer -= 2LL * HLDQuery(cen);
answer += pth[cen] * al;
//cerr << "nquery\n";
return answer * 2LL;
}
