【算法笔记】树上差分+树形DP

「妖怪が鍛えたこの楼観剣に 斬れぬものなど、あんまり無い！」

树上差分

树上差分分两种，点差分和边差分。

不管是哪一种，都是基于最基础的差分的。

只不过我们的操作对象从序列变成了树链。

点差分

假设说给你一棵树 \(T\)。

且 \(\forall u \in T\) 都有一个权值 \(val[u]\)

现在有 \(q\) 次操作，每一次操作 \(\operatorname{change}(u,v,d)\) 需要你修改 \(u \to v\) 的路径上的所有点的权值。

即令 \(\forall val[u]+d,(u\in \delta(u,v))\) 。

怎么做？

正常想法是 \(\texttt{dfs}\) 暴力修改。

显而易见，这做法受不住树链很长的多次询问 。

还有一种做法是先树剖然后套一个线段树。

但这里完全不在讨论范围内啊。

所以点差分就出现在了我们的眼前。

我们将一条树链拆成 \(A:(u,lca(u,v)),B:(v,lca(u,v))\) 这两部分。

那么设 \(c[u]\) 表示 \([u]\) 这个节点的增量（差分数组）。

我们有：

我们对于 \(A,B\) 的端点分别差分一下。

所以 \(c[u]=d,c[v]=d,c[lca]=-2\times d\)。

但是这个 \(\texttt{LCA}\) 本身就在树链 \(\delta(u,v)\) 上。

所以它自己也要加 \(d\) ，我们就给他加回去。

那么 \(c[u]=d,c[v]=d,c[lca]=-d\)。

但是你想想，我们差分之后肯定要还原，还原的时候肯定要 \(\texttt{dfs}\) ，从子树收集信息。

所以父节点的值是会被子树影响的。

所以我们还需要给 \(father(lca(u,v))-d\)。

这才是真正的点差分。

void dfs(int u,int fa){
	for(register int i=e[u].head;i;i=e[i].Next){
		int v=e[i].ver;
        if(v==fa) continue;
		dfs(v,u),c[u]+=c[v];//收集子树信息
	}
	a[u]+=c[u];//还原
	return;
} //在所有修改结束之后还原序列。

注意，差分的所有修改一定在查询之前，要不然你需要还原，修改多次。

还不如树剖+线段树。

边差分

点差分明白了，边差分也就十分类似。

之前做 P3627 [APIO2009]抢掠计划的时候。

用了一个思想叫“点权化边权”。

在这里我们反过来，“边权化点权”。

考虑任意的一条树边 \((u,v)\) ，一定满足它连接的是父亲和儿子（废话）。

那么这个边的“指向”就有唯一性。

所以我们把每一条树边的权值压到它指向的“儿子节点”。

特别的，因为树根没有父亲，所以它的权值为 \(0\)

这是候就有人想，既然边权化点权了，那我们能不能直接跑点差分？

不行。

(\(u\) 打错成 \(x\)了）

你仔细看看，lca的权值可是 \((lca,root)\) 的权值哦。

我哪里需要更新这条边？

所以相当于是在跑一个去掉 \(\texttt{LCA}\) 的点差分。

于是我们就不需要考虑 \(\texttt{LCA}\) 的权值和它对 \(father({\texttt{LCA}})\) 的影响。

直接 \(c[u]+d,c[v]+d,c[lca]-2\times d\) 即可。

然后也是利用子树上传信息还原序列。

树形DP

正常的线性DP都是在一个序列上进行决策和转移的。

那如果转到树上呢？

当然可以使用拓扑排序进行DP，不过这里我们讨论利用 \(\texttt{dfs}\) 实现的树形DP。

我们一般从叶子节点上推到根节点，也就是在递归之后利用子树信息更新父节点。

不过调用 \(\texttt{dfs}\) 的时候还是写 dfs(root)

所以说 \(f\) 的第一维一般是当前访问的节点（方便决策和讨论转移）。

那么这里以最经典的“没有上司的舞会”为例讨论一下树形DP。

description

solution

题中极度明确的说到了：从属关系构成一棵树。

而且父亲节点是否参加会影响儿子节点是否参加。

那么我们就从这两个“树形”限制入手。

先设 \(f[u]\) 表示节点 \(u\) 的最大权值。

诶，不对啊，这状态有问题吧，节点 \(u\) 的最大权值是什么，怎么来的？

很明显状态并没有设计完整，我们只考虑了“从属关系”这一条件，也就是考虑当前节点的位置，便于判断父亲节点。

所以利用第二个条件再加一维。

设 \(f[u][0/1]\) 表示 \(u\) 参加或者不参加舞会的最大快乐值。

嗯？还是不对，你这状态有个鬼用啊，参加不就是 \(r[u]\)，不参加不就是 \(0\) 吗？

你怎么用这个节点的决策更新它的父亲（儿子）的状态？

你怎么转移？

所以这个状态设计的还不够完善，为了想办法“决策”，

我们设 \(f[u][0/1]\) 表示以 \(u\) 为根的子树， \(u\) 参加或者不参加舞会取得的最大权值。

那么根据状态设计，我们分 \(f[u][0]\) 和 \(f[u][1]\) 两种情况来讨论。

如果 \(u\) 不参加舞会，那么它的儿子们都可以参加舞会。

但是我们注意到 \(r_i\) 可能是负数，所以要在儿子参加和不参加里面取个最大值然后再求和。

\(f[u][0]=\sum^{v=1}_{v\le \text{sonsize(u)}} \max(f[v][1],f[v][0])\)

然后如果 \(u\) 参加了舞会，那么它的儿子节点就都不会参加，但是它自己要参加。

所以 \(f[u][1]=\sum^{v=1}_{v\le \text{sonsize(u)}}f[v][0]+r_u\)

然后我们DP完了之后就在 \(f[root][0]\) 和 \(f[root][1]\) 之间取个最大值即可。

Code：

#include
using namespace std;

const int si=6e3+10;
struct Tree{
	int ver,head,Next;
}e[si*2];
int root=0,cnt=0;
void add(int u,int v){
	e[++cnt].ver=v,e[cnt].Next=e[u].head;
	e[u].head=cnt;
}

int r[si];
int f[si][2];
bool nrt[si];

void dp(int u,int fa){
	f[u][0]=0;
	f[u][1]=r[u];//注意这里不要放到里面，会多加
	for(register int i=e[u].head;i;i=e[i].Next){
		int v=e[i].ver;
		if(v==fa) continue;
		dp(v,u);
		f[u][0]+=max(f[v][1],f[v][0]);
		f[u][1]+=f[v][0];
	}
}

int n;
int main(){
	scanf("%d",&n);
	for(register int i=1;i<=n;++i){
		scanf("%d",&r[i]);
	}
	for(register int i=1;i

void dp(int u,int fa){
	f[u][1]=val[u];
	for(register int i=e[u].head;i;i=e[i].Next){
		int v=e[i].ver;
		if(v==fa) continue;
		dfs(v,u);
		for(register int j=m;j>=1;--j){
			for(register int k=0;k

void dp(int u,int fa){
	f[u][1]=val[u];
	for(register int i=e[u].head;i;i=e[i].Next){
		int v=e[i].ver;
		if(v==fa) continue;
		for(register int j=m;j>=0;--j){
			f[v][j]=f[u][j]+val[v];
		}
		dfs(v,u);
		for(register int j=m;j>=0;--j){
			f[u][j]=max(f[u][j],f[v][j-1]);
		}
	}
}

void dp(int u,int fa){
	for(register int i=e[u].head;i;i=e[i].Next){
		int v=e[i].ver;
		if(v==fa) continue;
		dp(v,u),f[u]=max(f[u],d[u]+d[v]+e[i].w);
		d[u]=max(d[u],d[v]+e[i].w);
	}
}
//也可以不用 f 直接写 res

void dfs(int u,int fa){
	siz[u]=1;
	for(register int i=e[u].head;i;i=e[i].Next){
		int v=e[i].ver;
		if(v==fa) continue;
		dfs(v,u);
		siz[u]+=siz[v];
	}
}
void dp(int u,int fa){
	for(register int i=e[u].head;i;i=e[i].Next){
		int v=e[i].ver;
		if(v==fa) continue;
		dp(v,u);
		f[u]=max(f[u],siz[v]);
	}
	f[u]=max(f[u],n-siz[u]);
}