这个世界有 n 个城市，这 n 个城市被恰好 \(n-1\) 条双向道路联通，即任意两个城市都可以 互相到达。同时城市 1 坐落在世界的中心，占领了这个城市就称霸了这个世界。
在最开始，这 n 个城市都不在任何国家的控制之下，但是随着社会的发展，一些城市会崛 起形成国家并夺取世界的霸权。为了方便，我们标记第 i 个城市崛起产生的国家为第 i 个国家。 在第 i 个城市崛起的过程中，第 i 个国家会取得城市 i 到城市 1 路径上所有城市的控制权。
新的城市的崛起往往意味着战争与死亡，若第 i 个国家在崛起中，需要取得一个原本被国 家 \(j(j≠i)\) 控制的城市的控制权，那么国家 i 就必须向国家 j 宣战并进行战争。
现在，可怜知道了，在历史上，第 i 个城市一共崛起了 \(a_i\) 次。但是这些事件发生的相对顺 序已经无从考究了，唯一的信息是，在一个城市崛起称霸世界之前，新的城市是不会崛起的。
战争对人民来说是灾难性的。可怜定义一次崛起的灾难度为崛起的过程中会和多少不同的国家进行战争（和同一个国家进行多次战争只会被计入一次）。可怜想要知道，在所有可能的崛 起顺序中，灾难度之和最大是多少。
同时，在考古学家的努力下，越来越多的历史资料被发掘了出来，根据这些新的资料，可怜会对 \(a_i\) 进行一些修正。具体来说，可怜会对\(a_i\) 进行一些操作，每次会将 \(a_x\) 加上 w。她希望 在每次修改之后，都能计算得到最大的灾难度。
然而可怜对复杂的计算并不感兴趣，因此她想让你来帮她计算一下这些数值。 对题面的一些补充：
第一行输入两个整数 n,m 表示城市个数和操作个数。
第二行输入 n 个整数表示 ai 的初始值。 接下来 n ? 1 行，每行输入两个整数 \(u_i, v_i\)(\(1\leq ui, vi \leq n\)) 描述了一条道路。
接下来 m 行每行输入两个整数 \(x_i\), \(w_i\) 表示将 \(a_{x_i}\) 加上 \(w_i\)。
输出共 \(m+1\) 行，第一行表示初始的 ai 的答案，接下来 m 行每行表示这次修正后的答案。
5 3
1 1 1 1 1
1 2
1 3
2 4
2 5
2 1
3 1
4 16
7
9
10在修正开始之前，如果按照所在城市 4, 1, 5, 3, 2 的顺序崛起，那么依次会和 0, 1, 2, 1, 2 个 国家进行战争。
这时一共会产生 6 对敌对关系。可以证明这是所有崛起顺序中的最大值。
\[ \min\{S_x-1,2*(S_x-\max\{a_x,\forall S_c\})\} \]
#include<bits/stdc++.h>
#define LL long long
LL in() {
char ch; LL x = 0, f = 1;
while(!isdigit(ch = getchar()))(ch == '-') && (f = -f);
for(x = ch ^ 48; isdigit(ch = getchar()); x = (x << 1) + (x << 3) + (ch ^ 48));
return x * f;
}
const int maxn = 4e5 + 10;
struct node {
node *ch[2], *fa;
LL tp, a, tot, siz;//维护子树a之和，siz记录虚子树的东西，tot是总共的和
node(LL tp = 0, LL a = 0, LL tot = 0, LL siz = 0): tp(tp), a(a), tot(tot), siz(siz) {}
void upd() {
tot = siz + a;
if(ch[0]) tot += ch[0]->tot;
if(ch[1]) tot += ch[1]->tot;
}
bool ntr() { return fa && (fa->ch[0] == this || fa->ch[1] == this); }
bool isr() { return fa->ch[1] == this; }
}pool[maxn];
struct EDGE {
int to;
EDGE *nxt;
EDGE(int to = 0, EDGE *nxt = NULL): to(to), nxt(nxt) {}
}*head[maxn];
void add(int from, int to) {
head[from] = new EDGE(to, head[from]);
}
void rot(node *x) {
node *y = x->fa, *z = y->fa;
bool k = x->isr(); node *w = x->ch[!k];
if(y->ntr()) z->ch[y->isr()] = x;
(x->ch[!k] = y)->ch[k] = w;
(y->fa = x)->fa = z;
if(w) w->fa = y;
y->upd(), x->upd();
}
void splay(node *o) {
while(o->ntr()) {
if(o->fa->ntr()) rot(o->isr() ^ o->fa->isr()? o : o->fa);
rot(o);
}
}
int n, m;
LL ans;
void dfs(node *x, node *fa) { //初始的ans
node *pos = x;
LL max = x->a;
for(EDGE *i = head[x - pool]; i; i = i->nxt) {
node *y = pool + i->to;
if(y == fa) continue;
dfs(y, x);
y->fa = x;
x->siz += y->tot; //刚开始都是虚边
if(max < y->tot) max = y->tot, pos = y; //找到max用来DP
}
if(max << 1 > (x->tot = x->siz + x->a)) { //取后面
ans += (x->tot - max) << 1;
if(x != pos) x->siz -= (x->ch[1] = pos)->tot; //子树大，连实边
else x->tp = 1; //自己大
}
else x->tp = 2, ans += x->tot - 1; //取前面
}
void access(node *x, LL w) {
for(node *y = NULL; x; x = (y = x)->fa) {
splay(x);
LL sum = x->tot - (x->ch[0]? x->ch[0]->tot : 0); //sum是原来子树的a之和（子树肯定比自己深度大，所以减去左子树）
//减去原来的贡献，通过type来搞
if(x->tp < 2) {
if(x->tp) ans -= (sum - x->a) << 1;
else ans -= (sum - (x->ch[1]? x->ch[1]->tot : 0)) << 1;
}
else ans -= sum - 1;
sum += w, x->tot += w; //进行修改
if(y) x->siz += w;
else x->a += w;
if(y && (y->tot << 1) > sum) { //是否应该改变实边所向
if(x->ch[1]) x->siz += x->ch[1]->tot;
x->siz -= (x->ch[1] = y)->tot;
}
if(x->ch[1] && (x->ch[1]->tot << 1) > sum) { //统计新贡献
x->tp = 0;
ans += (sum - x->ch[1]->tot) << 1;
}
else {
if(x->ch[1]) x->siz += x->ch[1]->tot, x->ch[1] = NULL;
if((x->a << 1) > sum) x->tp = 1, ans += (sum - x->a) << 1;
else x->tp = 2, ans += (sum - 1), x->ch[1] = 0;
}
}
}
int main() {
n = in(), m = in();
int x, y;
for(int i = 1; i <= n; i++) pool[i].a = in();
for(int i = 1; i < n; i++) x = in(), y = in(), add(x, y), add(y, x);
dfs(pool + 1, pool), printf("%lld\n", ans);
while(m --> 0) x = in(), y = in(), access(pool + x, y), printf("%lld\n", ans);
return 0;
}原文：https://www.cnblogs.com/olinr/p/10402115.html