#include "deliveries.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll LINF = (ll) 1e18;
struct node {
int l, r;
ll sum_t, sum_t_w, max_w, lazy;
node *left, *right;
} *root;
node *build(int l, int r, const vector<int> &t, const vector<ll> &w) {
if (l == r) return new node{l, r, t[l], t[l] * w[l], w[l], 0, 0, 0};
node *left = build(l, (l + r) / 2, t, w), *right = build((l + r) / 2 + 1, r, t, w);
return new node{l, r, left->sum_t + right->sum_t, left->sum_t_w + right->sum_t_w, max(left->max_w, right->max_w), 0, left, right};
}
void push(node *cur) {
if (cur->lazy == 0) return;
cur->sum_t_w += cur->lazy * cur->sum_t;
cur->max_w += cur->lazy;
if (cur->left) {
cur->left->lazy += cur->lazy;
cur->right->lazy += cur->lazy;
}
cur->lazy = 0;
}
void update(node *cur, int l, int r, int val) {
push(cur);
if (cur->l > r || cur->r < l) return;
if (l <= cur->l && cur->r <= r) {
cur->lazy += val;
push(cur);
return;
}
update(cur->left, l, r, val); update(cur->right, l, r, val);
cur->sum_t = cur->left->sum_t + cur->right->sum_t;
cur->sum_t_w = cur->left->sum_t_w + cur->right->sum_t_w;
cur->max_w = max(cur->left->max_w, cur->right->max_w);
}
ll query(node *cur, int l, int r) {
push(cur);
if (cur->l > r || cur->r < l) return 0;
if (l <= cur->l && cur->r <= r) return cur->sum_t_w;
return query(cur->left, l, r) + query(cur->right, l, r);
}
int n, cur_hld_pos = 0;
ll pre_ans = 0, sum_w = 0;
vector<int> p, w, subtree_size, heavy, up_edge, hld_head, hld_pos, hld_rev_pos;
vector<ll> subtree_sum, depth;
vector< vector< pair<int, int> > > g;
int find_last_large(node *cur) {
push(cur);
if (cur->l == cur->r) return hld_rev_pos[cur->l];
push(cur->left); push(cur->right);
if (2ll * cur->right->max_w > sum_w + 1) return find_last_large(cur->right);
return find_last_large(cur->left);
}
void dfs(int u) {
subtree_size[u] = 1;
subtree_sum[u] = w[u];
for (auto &[v, t] : g[u]) {
if (v == p[u]) continue;
up_edge[v] = t;
depth[v] = depth[u] + t;
p[v] = u;
dfs(v);
subtree_sum[u] += subtree_sum[v];
subtree_size[u] += subtree_size[v];
if (heavy[u] == -1 || subtree_size[v] > subtree_size[heavy[u]]) heavy[u] = v;
}
}
void hld_decompose(int u, int head) {
hld_head[u] = head;
hld_rev_pos[cur_hld_pos] = u;
hld_pos[u] = cur_hld_pos++;
if (heavy[u] != -1) hld_decompose(heavy[u], head);
for (auto &[v, t] : g[u]) {
if (v != p[u] && v != heavy[u]) hld_decompose(v, v);
}
}
void init(int N, std::vector<int> U, std::vector<int> V, std::vector<int> T, std::vector<int> W) {
n = N; w = W; g.resize(n);
for (int i = 0; i < n - 1; i++) {
g[U[i]].push_back({V[i], T[i]});
g[V[i]].push_back({U[i], T[i]});
}
p.assign(n, -1); subtree_size.resize(n); heavy.assign(n, -1); up_edge.assign(n, 0); depth.assign(n, 0); subtree_sum.assign(n, 0);
dfs(0);
hld_pos.reserve(n); hld_rev_pos.reserve(n); hld_head.resize(n);
hld_decompose(0, 0);
vector<int> hld_t(n); vector<ll> hld_w(n);
for (int i = 0; i < n; i++) {
hld_t[hld_pos[i]] = up_edge[i];
hld_w[hld_pos[i]] = subtree_sum[i];
pre_ans += subtree_sum[i] * up_edge[i];
sum_w += w[i];
}
root = build(0, n - 1, hld_t, hld_w);
}
long long max_time(int S, int X) {
int diff = X - w[S]; w[S] = X;
pre_ans += (ll) diff * depth[S];
sum_w += diff;
int u = S;
while (u != -1) {
update(root, hld_pos[hld_head[u]], hld_pos[u], diff);
u = p[hld_head[u]];
}
u = find_last_large(root);
ll ans = pre_ans + depth[u] * (sum_w + 1);
while (u != -1) {
ans -= 2ll * query(root, hld_pos[hld_head[u]], hld_pos[u]);
u = p[hld_head[u]];
}
return 2ll * ans;
}
