P4719 【模板】动态dp

\(\color{#0066ff}{ 题目描述 }\)

给定一棵\(n\)个点的树，点带点权。

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

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

\(\color{#0066ff}{输入格式}\)

第一行，\(n,m\)分别代表点数和操作数。

第二行，\(V_1,V_2,...,V_n\)，代表\(n\)个点的权值。

接下来\(n-1\)行，\(x,y\)，描述这棵树的\(n-1\)条边。

接下来\(m\)行，\(x,y\)，修改点xx的权值为\(y\)。

\(\color{#0066ff}{输出格式}\)

对于每个操作输出一行一个整数，代表这次操作后的树上最大权独立集。

保证答案在int范围内

\(\color{#0066ff}{输入样例}\)

10 10

-11 80 -99 -76 56 38 92 -51 -34 47

2 1

3 1

4 3

5 2

6 2

7 1

8 2

9 4

10 7

9 -44

2 -17

2 98

7 -58

8 48

3 99

8 -61

9 76

9 14

10 93

\(\color{#0066ff}{输出样例}\)

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

对于30%的数据，\(1\le n,m\le 10\)

对于60%的数据，\(1\le n,m\le 1000\)

对于100%的数据，\(1\le n,m\le 10^5\)

\(\color{#0066ff}{ 题解 }\)

动态DP就是带修改的DP

首先，考虑不带修改的DP

对于本题

设\(f[i][0]\)为以i为根子树不选i的ans，\(f[i][1]\)为以i为根子树选i的ans

转移

\(f[x][0]=\sum max(f[son][0],f[son][1])\)

\(f[x][1] = \sum f[son][0]+val[x]\)

我们进行树链剖分

定义\(g[x][0/1]\)为以x为根子树，只考虑轻儿子的ans

这个可以跟f一块求出，只有当儿子是轻儿子的时候才用儿子的f转移到当前的g

那么我们改写DP式子

\(f[x][0]=g[x][0]+max(f[son][0],f[son][1])\)

\(f[x][1]=g[x][1]+f[son][0]\)

然后每个点，我们维护一个矩阵，考虑转移

\(\left\{\begin{matrix} f[son][0] \\ f[son][1] \end{matrix}\right\} \to \left\{\begin{matrix} f[x][0] \\ f[x][1] \end{matrix}\right\}\)

由转移式子得出，需要取max和+

所以我们定义 * 为 + ， + 为取max

不难推出转移矩阵

\(\left\{\begin{matrix} g[x][0]& g[x][0]\\ g[x][1] & -inf \end{matrix}\right\}\)

因此\(\left\{\begin{matrix} g[x][0]& g[x][0]\\ g[x][1] & -inf \end{matrix}\right\} * \left\{\begin{matrix} f[son][0] \\ f[son][1] \end{matrix}\right\} = \left\{\begin{matrix} f[x][0] \\ f[x][1] \end{matrix}\right\}\)

可以发现，叶子节点的f和g是一样的，而且一条重链，必以叶子节点结束

所以我们按照树链剖分，用线段树维护矩阵的积，每条重链记录一下这条链的链尾的dfn

这样ans=1所在重链的矩阵的积的其中左面两个值的max

考虑修改

对于点x

可以发现，如果x是重儿子，那么所在重链的转移矩阵是毫无影响的

因为矩阵中都是g，而g是轻儿子的ans

那么我们每次只需修改一个点，然后跳到链顶，这时候，链顶的fa的矩阵需要改变

可以在改变前求出链顶矩阵，改变后求出链顶矩阵

然后根据DP式子，找到矩阵的变化量\(\Delta\)，其实就是减去原来这个儿子的贡献在加上新的贡献就行了

因为本题的DP都是取\(\sum\)，所以直接加减就行了

#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 = 1e5 + 100;

const int inf = 0x3f3f3f3f;

struct Matrix {

	int a[2][2];

	Matrix(int n = 0, int m = 0, int p = 0, int q = 0) {

		a[0][0] = n;

		a[0][1] = m;

		a[1][0] = p;

		a[1][1] = q;

	}

	friend Matrix operator * (const Matrix &c, const Matrix &d) {

		Matrix t(-inf, -inf, -inf, -inf);

		for(int i = 0; i <= 1; i++)

			for(int j = 0; j <= 1; j++)

				for(int k = 0; k <= 1; k++)

					t.a[i][j] = std::max(t.a[i][j], c.a[i][k] + d.a[k][j]);

		return t;

	}

	friend Matrix operator + (const Matrix &c, const Matrix &d) {

		return Matrix(c.a[0][0] + d.a[0][0], c.a[0][1] + d.a[0][1], c.a[1][0] + d.a[1][0], c.a[1][1] + d.a[1][1]);

	}

	friend Matrix operator - (const Matrix &c, const Matrix &d) {

		return Matrix(c.a[0][0] - d.a[0][0], c.a[0][1] - d.a[0][1], c.a[1][0] - d.a[1][0], c.a[1][1] - d.a[1][1]);

	}

}val[maxn];

struct Tree {

	int l, r;

	Tree *ch[2];

	Matrix val;

	Tree(int l = 0, int r = 0, Matrix c = Matrix(0, 0, 0, 0)): l(l), r(r), val(c) {

		ch[0] = ch[1] = NULL;

	}

	void *operator new (size_t) {

		static Tree *S = NULL, *T = NULL;

		return (S == T) && (T = (S = new Tree[1024]) + 1024), S++;

	}

	void upd() {

		val = ch[0]->val * ch[1]->val;

	}

};

Tree *root;

struct node {

	int to;

	node *nxt;

	node(int to = 0, node *nxt = NULL): to(to), nxt(nxt) {}

	void *operator new (size_t) {

		static node *S = NULL, *T = NULL;

		return (S == T) && (T = (S = new node[1024]) + 1024), S++;

	}

};

node *head[maxn];

int son[maxn], dep[maxn], siz[maxn], fa[maxn], n, m, c[maxn];

int top[maxn], dfn[maxn], redfn[maxn], e[maxn];

int f[maxn][2], g[maxn][2], cnt;

void add(int from, int to) {

	head[from] = new node(to, head[from]);

}

void dfs1(int x, int ft) {

	fa[x] = ft;

	dep[x] = dep[ft] + 1;

	siz[x] = 1;

	for(node *i = head[x]; i; i = i->nxt) {

		if(i->to == ft) continue;

		dfs1(i->to, x);

		siz[x] += siz[i->to];

		if(!son[x] || siz[i->to] > siz[son[x]]) son[x] = i->to;

	}

}

void dfs2(int x, int t) {

	top[redfn[dfn[x] = ++cnt] = x] = t;

	e[t] = dfn[x];

	if(son[x]) dfs2(son[x], t);

	for(node *i = head[x]; i; i = i->nxt)

		if(!dfn[i->to]) dfs2(i->to, i->to);

}

void dfs3(int x, int ft) {

	f[x][1] = g[x][1] = c[x];

	for(node *i = head[x]; i; i = i->nxt) {

		if(i->to == ft) continue;

		dfs3(i->to, x);

		f[x][1] += f[i->to][0];

		f[x][0] += std::max(f[i->to][0], f[i->to][1]);

		if(i->to != son[x]) {

			g[x][1] += f[i->to][0];

			g[x][0] += std::max(f[i->to][0], f[i->to][1]);

		}

	}

	val[x] = Matrix(g[x][0], g[x][0], g[x][1], -inf);

}

void build(Tree *&o, int l, int r) {

	o = new Tree(l, r, Matrix(0, 0, 0, 0));

	if(l == r) return (void)(o->val = val[redfn[l]]);

	int mid = (l + r) >> 1;

	build(o->ch[0], l, mid);

	build(o->ch[1], mid + 1, r);

	o->upd();

}

Matrix query(Tree *o, int l, int r) {

	if(o->r < l || o->l > r) return Matrix(0, -inf, -inf, 0);

	if(l <= o->l && o->r <= r) return o->val;

	return query(o->ch[0], l, r) * query(o->ch[1], l, r);

}

void change(Tree *o, int pos, Matrix v) {

	if(o->r < pos || o->l > pos) return;

	if(o->l == o->r) return (void)(o->val = v);

	change(o->ch[0], pos, v), change(o->ch[1], pos, v);

	o->upd();

}

Matrix query(int x) {

	return query(root, dfn[x], e[top[x]]);

}

void change(int x, int v) {

	val[x] = val[x] + Matrix(0, 0, -c[x] + v, 0);

	c[x] = v;

	int fx = top[x], ffx = fa[fx];

	while(1) {

		Matrix Old = query(fx);

		change(root, dfn[x], val[x]);

		if(!ffx) return;

		Matrix New = query(fx);

		val[ffx].a[0][0] += std::max(New.a[0][0], New.a[1][0]) - std::max(Old.a[0][0], Old.a[1][0]);

		val[ffx].a[0][1] = val[ffx].a[0][0];

		val[ffx].a[1][0] += New.a[0][0] - Old.a[0][0];

		x = ffx;

		fx = top[x];

		ffx = fa[fx];

	}

}

int main() {

	n = in(), m = in();

	for(int i = 1; i <= n; i++) c[i] = in();

	int x, y;

	for(int i = 1; i < n; i++) {

		x = in(), y = in();

		add(x, y), add(y, x);

	}

	dfs1(1, 0);

	dfs2(1, 1);

	dfs3(1, 0);

	build(root, 1, n);

	while(m --> 0) {

		x = in(), y = in();

		change(x, y);

		Matrix ans = query(1);

		printf("%d\n", std::max(ans.a[0][0], ans.a[1][0]));

	}

	return 0;

}

巴特西