#include "deliveries.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 1;
vector <pair <int, ll>> adj[N];
ll dep[N];
pair <ll, ll> e[N];
int nxt[N], sze[N], in[N], timer;
#define mid ((l + r) >> 1)
#define tl (node << 1)
#define tr (node << 1 | 1)
struct SegmentTree1 {
ll tree[N << 2], lazy[N << 2];
void prop (int l, int r, int node) {
if (l != r) {
lazy[tl] += lazy[node];
lazy[tr] += lazy[node];
}
tree[node] += (ll)(r - l + 1) * lazy[node];
lazy[node] = 0;
}
void update (int l, int r, int a, int b, ll c, int node) {
prop(l, r, node);
if (l > b || r < a) return;
if (l >= a && r <= b) {
lazy[node] += c;
prop(l, r, node);
return;
}
update(l, mid, a, b, c, tl);
update(mid + 1, r, a, b, c, tr);
tree[node] = tree[tl] + tree[tr];
}
ll get (int l, int r, int a, int b, int node) {
prop(l, r, node);
if (l > b || r < a) return 0;
if (l >= a && r <= b) return tree[node];
return get(l, mid, a, b, tl) + get(mid + 1, r, a, b, tr);
}
} cur;
struct SegmentTree2 {
ll tree[N << 2], sum[N << 2], lazy[N << 2], a[N];
void init (int l, int r, int node) {
if (l == r) {
sum[node] = a[l];
} else {
init(l, mid, tl); init(mid + 1, r, tr);
sum[node] = sum[tl] + sum[tr];
}
}
void prop (int l, int r, int node) {
if (l != r) {
lazy[tl] += lazy[node];
lazy[tr] += lazy[node];
}
tree[node] += sum[node] * lazy[node];
lazy[node] = 0;
}
void update (int l, int r, int a, int b, ll c, int node) {
prop(l, r, node);
if (l > b || r < a) return;
if (l >= a && r <= b) {
lazy[node] += c;
prop(l, r, node);
return;
}
update(l, mid, a, b, c, tl); update(mid + 1, r, a, b, c, tr);
tree[node] = tree[tl] + tree[tr];
}
ll get (int l, int r, int a, int b, int node) {
prop(l, r, node);
if (l > b || r < a) return 0;
if (l >= a && r <= b) return tree[node];
return get(l, mid, a, b, tl) + get(mid + 1, r, a, b, tr);
}
} cur2;
void dfs (int pos, int par) {
if (par != -1) {
for (int i = 0; i < (int)adj[pos].size(); i++) {
if (adj[pos][i].first == par) {
adj[pos].erase(adj[pos].begin() + i);
break;
}
}
}
sze[pos] = 1;
for (auto [j, w] : adj[pos]) {
dfs(j, pos);
sze[pos] += sze[j];
}
}
void dfs2 (int pos) {
in[pos] = timer++;
for (auto &j : adj[pos]) {
if (sze[j.first] > sze[adj[pos][0].first]) {
swap(adj[pos][0], j);
}
}
for (auto [j, w] : adj[pos]) {
dep[j] = w + dep[pos];
nxt[j] = (j == adj[pos][0].first ? nxt[pos] : j);
e[j] = {w, pos};
dfs2(j);
}
}
int n, t[N];
void init (int _N, vector <int> u, vector <int> v, vector <int> w, vector <int> T) {
n = _N;
for (int i = 0; i < n; i++) {
t[i] = T[i];
}
for (int i = 0; i < n - 1; i++) {
adj[u[i]].push_back({v[i], w[i]});
adj[v[i]].push_back({u[i], w[i]});
}
dfs(0, -1);
nxt[0] = 0;
dfs2(0);
for (int i = 1; i < n; i++) {
cur2.a[in[i]] = e[i].first;
}
cur2.init(0, n - 1, 1);
for (int i = 0; i < n; i++) {
int u = i;
while (nxt[u] != 0) {
cur.update(0, n - 1, in[nxt[u]], in[u], t[i], 1);
cur2.update(0, n - 1, in[nxt[u]], in[u], t[i], 1);
u = e[nxt[u]].second;
}
cur.update(0, n - 1, in[0], in[u], t[i], 1);
cur2.update(0, n - 1, in[0], in[u], t[i], 1);
}
}
ll get (int pos, int par) {
ll ret = 0;
for (auto [j, w] : adj[pos]) {
if (j != par) {
ll o = cur.get(0, n - 1, in[j], in[j], 1);
ll f = cur.get(0, n - 1, in[0], in[0], 1);
if (o * 2 > f) {
ret += get(j, pos);
ret += 2 * w * (f - 2 * o + 1);
break;
}
}
}
return ret;
}
ll max_time (int s, int x) {
int delta = x - t[s];
t[s] = x;
int u = s;
while (nxt[u] != 0) {
cur.update(0, n - 1, in[nxt[u]], in[u], delta, 1);
cur2.update(0, n - 1, in[nxt[u]], in[u], delta, 1);
u = e[nxt[u]].second;
}
cur.update(0, n - 1, in[0], in[u], delta, 1);
cur2.update(0, n - 1, in[0], in[u], delta, 1);
return 2 * cur2.get(0, n - 1, 0, n - 1, 1) + get(0, -1);
}
