P4338 [ZJOI2018]历史 LCT+树形DP

$\color{#0066ff}{ 题目描述 }$

这个世界有 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。她希望在每次修改之后，都能计算得到最大的灾难度。

然而可怜对复杂的计算并不感兴趣，因此她想让你来帮她计算一下这些数值。对题面的一些补充：

同一个城市多次崛起形成的国家是同一个国家，这意味着同一个城市连续崛起两次是不会和任何国家开战的：因为这些城市原来就在它的控制之下。
在历史的演变过程中，第 i 个国家可能会有一段时间没有任何城市的控制权。但是这并不意味着第 i 个国家灭亡了，在城市 i 崛起的时候，第 i 个国家仍然会取得 1 到 i 路径上的城市的控制权。

$\color{#0066ff}{输入格式}$

第一行输入两个整数 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$。

$\color{#0066ff}{输出格式}$

输出共 $m+1$ 行，第一行表示初始的 ai 的答案，接下来 m 行每行表示这次修正后的答案。

$\color{#0066ff}{输入样例}$

$\color{#0066ff}{输出样例}$

$\color{#0066ff}{数据范围与提示}$

在修正开始之前，如果按照所在城市 4, 1, 5, 3, 2 的顺序崛起，那么依次会和 0, 1, 2, 1, 2 个国家进行战争。

这时一共会产生 6 对敌对关系。可以证明这是所有崛起顺序中的最大值。

P4338 [ZJOI2018]历史 LCT+树形DP

$\color{#0066ff}{ 题解 }$

简单来说，题意就是给你每个点可以access的次数，还有修改，让你找到最优的access的顺序，使得虚实变换的次数最多

考虑每个点的子树。假设已经对所有子树中的点构造出了一个最优顺序（一个序列），那么一定不会和它的所有祖先的子树中的最优序列产生冲突。

所以我们考虑一个点x，能对x的实子边产生影响的，是x的所有子树和x本身（access（x）后x无实子边）

每次切换会对ans有1的贡献，显然同一子树的影响是相同的

因此我们让不同的子树或x交替进行access，这样产生的贡献才最多

当没有某棵子树的a之和或者x的a过大时，可以构造出（除了第一次）每个access都用贡献的方案

反之，当总和大于所有子树总和的一半时，就不行了，a之和特别大的那个子树（或x）一定有几次access是没有贡献的，设S为子树a之和，c为x的每棵子树，则贡献为

\[\min\{S_x-1,2*(S_x-\max\{a_x,\forall S_c\})\}
\]

这样DP就能把不带修改的分拿到了

现在考虑修改

首先，对于x的a加上w，只会对x到根的路径上的节点产生影响

因为我们只是加上一个值，所以如果某些子树的a之和大于一半，把a带进去发现贡献是不变的

某个子树的a之和大于总和一半？？？这是树剖的轻重边划分啊

所以如果某个子树的a之和大于总和一半，就连重边，否则就是轻边

于是我们在全局保存一个ans，access的时候找到虚边，直接减去原来的贡献，然后用w进行修改，判断是否要切换虚实边，并让ans加上新的贡献即可

可以设一个type表示当前点是哪个类型（某子树极大，自己极大，都不怎么大）

#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;

}