#include "deliveries.h"
#include "bits/stdc++.h"
using namespace std;
#define ar array
typedef long long ll;
//~ #define int ll
const int N = 1e5 + 5;
int n, cur;
ll tot;
vector<vector<ar<int, 2>>> edges;
vector<int> w;
vector<ar<int, 2>> par;
vector<ll> sub;
struct ST{
ll Max[N << 2], sum[N << 2], f[N << 2], b[N << 2];
void set(int i, int v, int lx, int rx, int x){
if(lx == rx) {
b[x] = v; return;
}
int m = (lx + rx) >> 1;
if(i <= m) set(i, v, lx, m, x << 1);
else set(i, v, m + 1, rx, x << 1 | 1);
b[x] = b[x << 1] + b[x << 1 | 1];
} void set(int i, int v) { set(i, v, 0, N, 1); }
void push(int x, int lx, int rx){
if(lx == rx) return;
Max[x << 1] += f[x], Max[x << 1 | 1] += f[x];
sum[x << 1] += b[x << 1] * f[x];
sum[x << 1 | 1] += b[x << 1 | 1] * f[x];
f[x << 1] += f[x], f[x << 1 | 1] += f[x];
f[x] = 0;
}
void add(int l, int r, int v, int lx, int rx, int x){
if(lx > r || rx < l) return;
if(lx >= l && rx <= r){
Max[x] += v;
sum[x] += b[x] * v;
f[x] += v;
return;
}
int m = (lx + rx) >> 1;
push(x, lx, rx);
add(l, r, v, lx, m, x << 1);
add(l, r, v, m + 1, rx, x << 1 | 1);
Max[x] = max(Max[x << 1], Max[x << 1 | 1]);
sum[x] = sum[x << 1] + sum[x << 1 | 1];
} void add(int l, int r, int v) { add(l, r, v, 0, N, 1); }
ll get(int l, int r, int lx, int rx, int x){
if(lx > r || rx < l) return 0ll;
if(lx >= l && rx <= r) return sum[x];
int m = (lx + rx) >> 1;
push(x, lx, rx);
return get(l, r, lx, m, x << 1) + get(l, r, m + 1, rx, x << 1 | 1);
} ll get(int l, int r) { return get(l, r, 0, N, 1) ; }
ll get_(int l, int r, int lx, int rx, int x){
if(lx > r || rx < l ) return 0ll;
if(lx >= l && rx <= r) return Max[x];
int m = (lx + rx) >> 1;
push(x, lx, rx);
return max(get_(l, r, lx, m, x << 1), get_(l, r, m + 1, rx, x << 1 | 1));
} ll get_(int l, int r) { return get_(l, r, 0, N, 1); }
int big(int v, int lx, int rx, int x){
if(lx == rx) return lx;
int m = (lx + rx) >> 1;
push(x, lx, rx);
if(Max[x << 1 | 1] >= v) return big(v, m + 1, rx, x << 1 | 1);
else return big(v, lx, m, x << 1);
}
int big(int v) { return big(v, 0, N, 1); }
}tree;
vector<int> cnt, hev, head, pos, ver;
vector<ll> pref;
void init(int N, vector<int> u, vector<int> v, vector<int> t, vector<int> W) {
w = W; n = N;
edges.resize(n);
sub.resize(n);
par.resize(n);
cnt.resize(n), hev.resize(n);
head.resize(n), pos.resize(n), ver.resize(n);
pref.resize(n);
tot = 2;
for(int i=0;i<n;i++) tot += w[i];
for(int i=0;i + 1<n;i++){
edges[u[i]].push_back({v[i], 2 * t[i]});
edges[v[i]].push_back({u[i], 2 * t[i]});
}
function<void(int, int)> dfs = [&](int u, int p){
sub[u] = w[u] + (u == 0) * 2;
cnt[u] = 1, hev[u] = -1;
for(auto [x, c] : edges[u]){
if(x == p) continue;
par[x] = {u, c};
pref[x] = pref[u] + c;
dfs(x, u);
if(hev[u] == -1 || cnt[x] > cnt[hev[u]]) hev[u] = x;
cnt[u] += cnt[x];
sub[u] += sub[x];
}
};
dfs(0, 0);
int last = 0;
function<void(int, int, int)> dec = [&](int u, int p, int P){
pos[u] = last++, ver[pos[u]] = u, head[u] = P;
if(~hev[u]){
dec(hev[u], u, P);
}
for(auto [x, c] : edges[u]){
if(x == p || x == hev[u]) continue;
dec(x, u, x);
}
};
dec(0, 0, 0);
for(int i=0;i<n;i++){
tree.set(pos[i], par[i][1]);
}
for(int i=0;i<n;i++){
tree.add(pos[i], pos[i], sub[i]);
}
//~ for(int i=0;i<n;i++){
//~ cout<<sub[i]<<" ";
//~ } cout<<endl;
//~ for(int i=0;i<n;i++){
//~ cout<<par[i][1]<<" ";
//~ } cout<<endl;
//~ for(int i=0;i<n;i++){
//~ cout<<tree.get(pos[i], pos[i])<<" ";
//~ } cout<<endl;
//~ for(int i=0;i<n;i++){
//~ cout<<tree.get_(pos[i], pos[i])<<" ";
//~ }
//~ cout<<endl;
}
ll get(int u){
ll res = 0;
while(head[u]){
res += tree.get(pos[head[u]], pos[u]);
u = par[head[u]][0];
}
res += tree.get(pos[head[u]], pos[u]);
return res;
}
void add(int u, int x){
while(head[u]){
tree.add(pos[head[u]], pos[u], x);
u = par[head[u]][0];
}
tree.add(pos[head[u]], pos[u], x);
}
ll max_time(int s, int x) {
x = -w[s] + x;
tot += x;
w[s] += x;
add(s, x);
//~ cout<<tot<<" "<<(tot + 1) / 2<<"\n";
//~ for(int i=0;i<n;i++){
//~ cout<<tree.get_(i, i)<<" ";
//~ } cout<<"\n";
//~ cout<<tree.Max[1]<<endl;
//~ cout<<(tot + 1) / 2<<endl;
//~ cout<<tree.big((tot + 1) / 2)<<endl;;
int cen = ver[tree.big((tot + 1) / 2)];
//~ cout<<cen<<" "<<tree.sum[1]<<" "<<(tot - 1) * pref[cen]<<" "<<get(cen)<<"\n";
ll res = tree.sum[1] + (tot - 1) * pref[cen];
res -= get(cen) * 2;
return res;
}
