OI - "动态 DP"&动态树分治(洛谷) | Lucky_Glass's Blog

以心为名，名为爱惜

0%

OI - "动态 DP"&动态树分治(洛谷)

发表于 分类于 Valine：

口胡起来倒是挺快乐的，码代码就……

# 题面

> 洛谷 P4719

点击展开/折叠题面

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

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

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

# 解析

如果没有修改操作，这就是一个简单的树的独立集DP，即 $f_{u,0},f_{u,1}$ 分别表示子树 u 中，节点 u 不选/选的最大权独立集的权。

然后就可以写出一个 DP 转移式：

既然这道题是动态 DP 的模板题，而我们知道动态 DP 经常用线段树维护DP转移，迁移到树上就是树链剖分，因此我们要处理出 u 的DP值与 u 的重儿子的DP值之间的关系。

记 $son’_u$ 是 u 的轻儿子的点集，则定义 $g_{u,0},g_{u,1}$：

> Tab. $wei_u$ 表示 u 的重儿子

则有：

再构造转移矩阵：

> Tab. 下面记 $M_u$ 表示中间那个 $2\times2$ 的转移矩阵

接下来我们对整棵树重链剖分，设以 $u$ 为 $top$ 的重链的链尾为 $bot_u$。然后稍加推导，我们发现：

所以我们要算点 $1$ 的DP值，只需要查 $1$ 的重链的 $\prod M_x$。

然后如何修改呢？

不妨设直接修改点权的点为 $u$，可以用一张图概括树链剖分维护的矩阵的改变情况：

png1

我们发现，只有轻儿子的 $f$ 改变才会使其父节点的 $g$ 改变，从而使其父亲的 $M$ 改变。

在上图中，修改 $val_U$ 后，直接影响到 $g_{U,1}$（即 $M_U$ 会改变）。间接影响到的是 $f_T$，从而影响到 $g_F$（即 $M_T$）。

$M_F$ 改变后，又会影响到 $F$ 的重链顶点的 $f$，则重链顶点的父亲的 $g$ 就会改变……一直到重链顶点是 $1$，因为 $1$ 没有父亲，所以不会有节点的 $M$ 会改变。

根据重链剖分的性质，一次修改只有 $O(\log n)$ 的点的 $M$ 会改变，所以复杂度正确。

# 源代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
/*Lucky_Glass*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=1e5+10,INF=1e9+10;
#define maxc(a,b) (a=max(a,b))

int n,m,ndfn;
int val[N];
int dfn[N],tp[N],dep[N],siz[N],anc[N],wei[N],idfn[N],bot[N];
int f[N][2],g[N][2];

struct GRAPH{
	int head[N],nxt[N<<1],to[N<<1],ncnt;
	void AddEdge(int u,int v){
		int p=++ncnt,q=++ncnt;
		nxt[p]=head[u],to[p]=v,head[u]=p;
		nxt[q]=head[v],to[q]=u,head[v]=q;
	}
	int operator [](const int &u){return head[u];}
}Gr;

struct MATRIX{
	int rol,col,mt[2][2];
	int* operator [](const int &i){return mt[i];}
	void Init(int r,int c){
		rol=r,col=c;
		for(int i=0;i<r;i++)
			for(int j=0;j<c;j++)
				mt[i][j]=-INF;
	}
	MATRIX operator *(MATRIX B){
		MATRIX ret;ret.Init(rol,B.col);
		for(int i=0;i<rol;i++)
			for(int j=0;j<B.col;j++)
				for(int k=0;k<col;k++)
					if(mt[i][k]!=-INF && B[k][j]!=-INF)
						maxc(ret[i][j],mt[i][k]+B[k][j]);
		return ret;
	}
};

struct SEGTREE{
	MATRIX num[N<<1];
	#define idx(l,r) (((l)!=(r))|((l)+(r)))
	void Update(int u,int po){
		num[u].Init(2,2);po=idfn[po];
		num[u][0][0]=g[po][0],num[u][0][1]=g[po][0];
		num[u][1][0]=g[po][1],num[u][1][1]=-INF;
	}
	void PushUp(int le,int ri){
		int mi=(le+ri)>>1;
		num[idx(le,ri)]=num[idx(le,mi)]*num[idx(mi+1,ri)];
	}
	void Build(int le,int ri){
		int u=idx(le,ri);
		if(le==ri){Update(idx(le,ri),le);return;}
		int mi=(le+ri)>>1;
		Build(le,mi),Build(mi+1,ri);
		PushUp(le,ri);
		// printf("%d %d %d %d\n",num[u][0][0],num[u][0][1],num[u][1][0],num[u][1][1]);
	}
	MATRIX Query(int le,int ri,int Le,int Ri){
		if(Le<=le && ri<=Ri) return num[idx(le,ri)];
		int mi=(le+ri)>>1;
		if(Ri<=mi) return Query(le,mi,Le,Ri);
		if(mi<Le) return Query(mi+1,ri,Le,Ri);
		return Query(le,mi,Le,Ri)*Query(mi+1,ri,Le,Ri);
	}
	void Modify(int le,int ri,int po){
		if(le==ri){Update(idx(le,ri),le);return;}
		int mi=(le+ri)>>1;
		if(po<=mi) Modify(le,mi,po);
		else Modify(mi+1,ri,po);
		PushUp(le,ri);
	}
}Se;

void MModify(int u,int key){
	g[u][1]+=key-val[u];val[u]=key;
	Se.Modify(1,n,dfn[u]);
	while(tp[u]!=1){
		u=tp[u];
		MATRIX res=Se.Query(1,n,dfn[u],dfn[bot[u]]);
		int fa=anc[u];
		g[fa][0]-=max(f[u][0],f[u][1]);
		g[fa][1]-=f[u][0];
		f[u][0]=res[0][0],f[u][1]=res[1][0];
		// printf("! [%d] %d %d\n",u,f[u][0],f[u][1]);
		g[fa][0]+=max(f[u][0],f[u][1]);
		g[fa][1]+=f[u][0];
		Se.Modify(1,n,dfn[fa]);
		u=fa;
	}
}
MATRIX MQuery(int u){return Se.Query(1,n,1,dfn[u]);}

inline int Ri(){
	register int r=0,c=getchar(),b=1;
	while(c<'0' || '9'<c) b=c=='-'? -1:b,c=getchar();
	while('0'<=c && c<='9') r=(r<<1)+(r<<3)+c-'0',c=getchar();
	return r*b;
}
void DFS(int u,int fa){
	siz[u]=1;dep[u]=dep[fa]+1;anc[u]=fa;
	f[u][1]=val[u];
	for(int it=Gr[u];it;it=Gr.nxt[it]){
		int v=Gr.to[it];
		if(v==fa) continue;
		DFS(v,u);
		f[u][0]+=max(f[v][0],f[v][1]);
		f[u][1]+=f[v][0];
		siz[u]=siz[u]+siz[v];
		if(siz[wei[u]]<siz[v]) wei[u]=v;
	}
}
void DFS2(int u,int tp_){
	tp[u]=tp_;idfn[dfn[u]=++ndfn]=u;
	g[u][1]=val[u];
	if(wei[u]) DFS2(wei[u],tp_);
	else{
		bot[tp_]=u;
		return;
	}
	for(int it=Gr[u];it;it=Gr.nxt[it]){
		int v=Gr.to[it];
		if(v==wei[u] || v==anc[u]) continue;
		g[u][0]+=max(f[v][0],f[v][1]);
		g[u][1]+=f[v][0];
		DFS2(v,v);
	}
}
int main(){
	// freopen("input.txt","r",stdin);
	n=Ri(),m=Ri();
	for(int i=1;i<=n;i++) val[i]=Ri();
	for(int i=1;i<n;i++) Gr.AddEdge(Ri(),Ri());
	DFS(1,0),DFS2(1,1);
	Se.Build(1,n);
	while(m--){
		int u=Ri(),key=Ri();
		MModify(u,key);
		MATRIX res=MQuery(bot[1]);
		printf("%d\n",max(res[0][0],res[1][0]));
	}
	return 0;
}

THE END

Thanks for reading!

> Linked 小丑的品格-网易云