ZJOI2018 历史

Vexoben

Mar 3, 2019

It takes 9 minutes to read this article.

题目连接:ZJOI2018 历史

(刷新以获取数学公式)

题意

给定一棵 $n$ 个节点的树和一个长度为 $n$ 的数组 $a_i$ , $m$ 次操作,每次会将一个 $a_x$ 增加 $w$ ,在修改后要求输出:如果以 $1$ 为根,对第 $i$ 个节点要进行 $a_i$ 次LCT的 $Access$ 操作(顺序任意),最多可以使轻重边切换多少次.

数据范围: $n,m≤400000$

题解

有一个显然的结论:每个节点轻重边切换次数对于答案的影响是独立的.因为一个节点轻重边切换需要分别对它两个子树中的节点 $Access$ ,而在这之间可以 $Access$ 不在这个子树中的节点,从而在保证该节点答案最大的同时最大化其它节点的答案.

这样我们就可以处理没有修改的情况了.设子树 $x$ 中一共要 $Access$ 的次数为 $s$ ,它的子树中(包括节点 $x$ 本身)最多要 $Access$ 的次数为 $t$ ,当 $2t≤s+1$ 时,答案是 $s-1$ ,否则答案为 $2(s-t)$

怎么处理修改呢?这里出题人就有了一个骚操作.

如果一个节点是 $2t>s+1$ 的情况,就在它和那个要 $Access$ 次数最多的孩子之间连一条重边.修改时,如果经过一条重边是不会影响答案的.同时很容易发现一个点到根的路径上轻边的条数是 $O(\sum a_i)$ 级别的,因此可以直接树剖+二分做到 $O(nlog^2n)$

复杂度更低的做法是用LCT代替树剖.将每一条重链用Splay维护,用类似于 $Access$ 的方式进行修改.不过,它并不会将所有经过的轻边都改为重边.因为不(wo)可(ye)描(bu)述(hui)的原因,复杂度就降低到了 $O(nlogn)$

#pragma GCC optimize("2,Ofast,inline")
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 4e5 + 10;

LL ans, a[N];

template<typename T> void read(T &x) {
	char c = getchar();
	while (c < '0' || c > '9') c = getchar();
	for (x = 0; c >= '0' && c <= '9'; c = getchar())
		x = (x << 3) + (x << 1) + c - '0';
}

namespace LCT {
	int fa[N], hs[N], ch[N][2];
	LL res[N], sum[N], tag[N];

	void Calcans(int x) {
		ans -= res[x];
		if (hs[x]) res[x] = 2 * (sum[x] - sum[hs[x]]);
		else if (a[x] * 2 >= sum[x] + 1) res[x] = 2 * (sum[x] - a[x]);
		else res[x] = sum[x] - 1;
		ans += res[x];
	}

	int Isroot(int x) {
		return (ch[fa[x]][0] != x) && (ch[fa[x]][1] != x);
	}

	int Get(int x) {
		return (ch[fa[x]][1] == x);
	}

	void Pushdown(int x) {
		if (x && tag[x]) {
			sum[x] += tag[x];
			tag[ch[x][0]] += tag[x];
			tag[ch[x][1]] += tag[x];
			tag[x] = 0;
		}
	}

	void Rotate(int x) {
		int y = fa[x], z = fa[y], k = Get(x);
		fa[x] = z;
		if (!Isroot(y)) ch[z][Get(y)] = x;
		fa[ch[x][k ^ 1]] = y;
		ch[y][k] = ch[x][k ^ 1];
		ch[x][k ^ 1] = y;
		fa[y] = x;
	}

	void Pushall(int x) {
		static int top, st[N];
		st[top = 1] = x;
		for (int i = x; !Isroot(i); i = fa[i]) {
			st[++top] = fa[i];
		}
		while (top) Pushdown(st[top--]);
	}
	
	void Splay(int x) {
		Pushall(x);
		for (; !Isroot(x); Rotate(x)) {
			if (!Isroot(fa[x])) {
				Get(x) == Get(fa[x]) ? Rotate(fa[x]) : Rotate(x);
			}
		}
	}

	int Find(int x)  {
		while (ch[x][0]) {
			Pushdown(x);
			x = ch[x][0];
		}
		Pushdown(x);
		return x;
	}

	void Access(int x, int w) {
		int i;
		a[x] += w;
		for (i = 0; x; i = x, x = fa[x]) {
			Splay(x);
			sum[x] += w; tag[ch[x][0]] += w;
			if (hs[x]) {
				Pushall(hs[x]);
				if (sum[hs[x]] * 2 < sum[x] + 1) {
					hs[x] = 0;
					ch[x][1] = 0;
				}
			}
			int t = Find(i);
			if (sum[t] * 2 >= sum[x] + 1) {
				hs[x] = t;
				ch[x][1] = i;
			}
			Calcans(x);
		}
	}
}

namespace Prework {
	int E, fir[N], nex[N << 1], arr[N << 1];

	inline void Add_Edge(int x, int y) {
		nex[++E] = fir[x];
		fir[x] = E; arr[E] = y;
	}

	void dfs(int x, int fa) {
		if (fa) LCT::fa[x] = fa;
		LCT::sum[x] = a[x];
		for (int i = fir[x]; i; i = nex[i]) {
			if (arr[i] == fa) continue;
			dfs(arr[i], x);
			LCT::sum[x] += LCT::sum[arr[i]];
		}
		for (int i = fir[x]; i; i = nex[i]) {
			if (arr[i] == fa) continue;
			if (LCT::sum[arr[i]] * 2 >= LCT::sum[x] + 1) {
				LCT::hs[x] = arr[i];
				LCT::ch[x][1] = arr[i];
			}
		}
		LCT::Calcans(x);
	}

	void main(int &n, int &m) {
		read(n); read(m);
		for (int i = 1; i <= n; ++i) {
			read(a[i]);
		}
		for (int i = 1; i < n; ++i) {
			int x, y;
			read(x); read(y);
			Add_Edge(x, y);
			Add_Edge(y, x);
		}
		dfs(1, 0);
		printf("%lld\n", ans);
	}
}

int main() {
	static int n, m;
	Prework::main(n, m);
	while (m--) {
		int x, w;
		read(x); read(w);
		LCT::Access(x, w);
		printf("%lld\n", ans);
	}
	return 0;
}