【模板】"动态 DP"&动态树分治

题目描述

给定一棵 $n$ 个点的树，点带点权。

有 $m$ 次操作，每次操作给定 $x,y$ ，表示修改点 $x$ 的权值为 $y$ 。

你需要在每次操作之后求出这棵树的最大权独立集的权值大小。

$1\le n,m\le 10^5$ ， $1 \leq u, v , x \leq n$ ， $-10^2 \leq a_i, y \leq 10^2$ 。

题解

对于没有修改操作，有 DP 设 $f_{i,0/1}$ 表示在以 $i$ 为根的子树中选不选 $i$ 的最大大小。

$$f_{u, 0} = \sum_{v\in\text{son}(u)} \max(f_{v, 0}, f_{v, 1}) $$

$$f_{u, 1} = \sum_{v\in\text{son}(u)} f_{v, 0}+a_u $$

带修后为了方便数据结构维护信息，再设 $g_{u, 0/1}$ 表示在 $u$ 及其所有轻儿子构成的子树，选不选 $u$ 最大大小。

$$f_{u, 0} = g_{u, 0} + \max(f_{v, 0}, f_{v, 1}) $$

$$f_{u, 1} = g_{u, 1} + a_u + f_{v, 0} $$

其中 $v$ 是重儿子。

然后用全局平衡二叉树维护，对于修改，每个结点用两个矩阵来分别维护重儿子和轻儿子（包括 $u$ ）的 $f,g$ ，转移时广义矩乘即可。

代码

const int N = 1e6 + 5, M = 3;

inline ll Read() {
	ll x = 0, f = 1;
	char c = getchar();
	while (c != '-' && (c < '0' || c > '9')) c = getchar();
	if (c == '-') f = -f, c = getchar();
	while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
	return x * f;
}

namespace Main {
	struct Matrix {
		int n, m;
		int mat[M][M];
		int* operator [](int d) { return mat[d]; }
		Matrix() {n=m=2;}
		void Output() {
			for (int i = 1; i <= n; i++, putchar(10))
				for (int j = 1; j <= m; j++)
					printf ("%d ", mat[i][j]);
		}
	};
	Matrix operator * (Matrix a, Matrix b) {
		Matrix c; c.n = a.n, c.m = b.m;
		for (int i = 1; i <= c.n; i++)
			for (int j = 1; j <= c.m; j++) {
				c[i][j] = -0x3FFFFFFF;
				for (int k = 1; k <= c.m; k++)
					c[i][j] = max(c[i][j], a[i][k] + b[k][j]);
			}
		return c;
	}
	struct Edge {
		int to, nxt;
	};
	int n, m, a[N];
	struct GBT {
		int head[N], tot;
		Edge e[N << 1];
		void add_edge (int u, int v) {
			e[++tot] = (Edge) {v, head[u]}, head[u] = tot;
		}

		int ch[N][2], tfa[N]; //on BST
		Matrix lm[N], hm[N];

		int dep[N], siz[N], lsiz[N], son[N];
		void dfs1 (int u, int fa) {
			dep[u] = dep[fa] + 1;
			siz[u] = 1;
			for (int i = head[u]; i; i = e[i].nxt) {
				int v = e[i].to;
				if (v == fa) continue;
				dfs1 (v, u);
				siz[u] += siz[v];
				if (!son[u] || siz[v] > siz[son[u]]) son[u] = v;
			}
			lsiz[u] = siz[u] - siz[son[u]];
		}
		int f[N][2], g[N][2];
		void dfs2 (int u, int fa) {
			f[u][0] = g[u][0] = 0;
			f[u][1] = g[u][1] = a[u];
			if (son[u]) {
				dfs2 (son[u], u);
				f[u][0] += max(f[son[u]][0], f[son[u]][1]);
				f[u][1] += f[son[u]][0];
			}
			for (int i = head[u]; i; i = e[i].nxt) {
				int v = e[i].to;
				if (v == fa || v == son[u]) continue;
				dfs2 (v, u);
				f[u][0] += max(f[v][0], f[v][1]);
				f[u][1] += f[v][0];
				g[u][0] += max(f[v][0], f[v][1]);
				g[u][1] += f[v][0];
			}
		}
		void init () {
			dfs1(1, 0);
			dfs2(1, 0);
			for (int i = 1; i <= n; i++) {
				lm[i][1][1] = lm[i][1][2] = g[i][0];
				lm[i][2][1] = g[i][1], lm[i][2][2] = -0x3FFFFFFF;
				if (!son[i]) lm[i][1][2] = -0x3FFFFFFF;
			}
			// for (int i = 1; i <= n; i++) lm[i].Output();
		}
		void pushup(int u) {
			hm[u] = lm[u];
			if (ch[u][0]) hm[u] = hm[ch[u][0]] * hm[u];
			if (ch[u][1]) hm[u] = hm[u] * hm[ch[u][1]];
		}
		int get_max2 (int u) { return max(hm[u][1][1], hm[u][1][2]); }
		int get_max1 (int u) { return max(get_max2(u), hm[u][2][1]); }

		int stk[N], top;
		bool vis[N];
		int SBuild (int l, int r) {
			if (l > r) return 0;
			int tot = 0;
			for (int i = l; i <= r; i++) tot += lsiz[stk[i]];
			for (int i = l, sum = lsiz[stk[l]]; i <= r; i++, sum += lsiz[stk[i]])
				if (sum * 2 >= tot) {
					ch[stk[i]][0] = SBuild(l, i - 1), ch[stk[i]][1] = SBuild(i + 1, r);
					tfa[ch[stk[i]][0]] = tfa[ch[stk[i]][1]] = stk[i];
					pushup(stk[i]);
					return stk[i];
				}
			return 0;
		}
		int Build (int u) {
			for (int p = u; p; p = son[p]) vis[p] = 1;
			for (int p = u; p; p = son[p])
				for (int i = head[p]; i; i = e[i].nxt) {
					int v = e[i].to;
					if (vis[v]) continue;
					tfa[Build(v)] = p;
				}
			top = 0;
			for (int p = u; p; p = son[p]) stk[++top] = p;
			int root = SBuild(1, top);
			return root;
		}
		void Modify (int u, int val) {
			lm[u][2][1] += val - a[u];
			a[u] = val;
			for (int p = u; p; p = tfa[p]) {
				if (tfa[p] && ch[tfa[p]][0] != p && ch[tfa[p]][1] != p) {
					lm[tfa[p]][1][1] -= get_max1(p);
					lm[tfa[p]][1][2] = lm[tfa[p]][1][1];
					lm[tfa[p]][2][1] -= get_max2(p);
					pushup(p);
					lm[tfa[p]][1][1] += get_max1(p);
					lm[tfa[p]][1][2] = lm[tfa[p]][1][1];
					lm[tfa[p]][2][1] += get_max2(p);
				} else pushup(p);
			}
		}
	} gbt;
	int main () {
		n = Read(), m = Read();
		for (int i = 1; i <= n; i++) a[i] = Read();
		for (int i = 1; i < n; i++) {
			int u = Read(), v = Read();
			gbt.add_edge(u, v);
			gbt.add_edge(v, u);
		}
		gbt.init();
		int root = gbt.Build(1);
		for (int lstans = 0; m--; ) {
			int u = Read(), v = Read();
			gbt.Modify(u, v);
			printf ("%d\n", lstans = gbt.get_max1(root));
		}
		return 0;
	}
}

int main () {
//	freopen(".in", "r", stdin);
//	freopen(".out", "w", stdout);
	Main::main();
	return 0;
}