洛谷 P1122 最大子树和 题解

一道入门的树形DP。

首先我们对于数据进行有序化处理,这便于我们利用数据结构特点(可排序性)来发觉数据性质(有序、单调、子问题等等性质),以便于后续的转化、推理和处理。有序化可以“转化和创造”性质

首先将视角从无根树切换为有根树,这样我们就可以得到一个带有最优子结构、无后效性、子问题重叠性的结构——一个根和一堆子树。

由于我们是要求联通分量的最大值,我们观察到每一个联通分量都可以看做一个有根树,这就保证了树形DP的正确性。(后面会再解释)

不难想到令\(f_i\)表示包含该位置的、以\(i\)号节点为根的子树的最大值。

这里的“不难想到”其实有两种想法——第一种是树形DP的一般思路就是子啊一棵子树内处理根与子树的关系,这是一种常见的经验或者说手法。第二种想法就是说,连通分量可以转化成更小的联通分量,加上有序化之后,变成了子树层层求解。

我们考虑每一棵子树,不难发现初始化每个节点就是根节点自己的值,然后对于每一棵向下连接根节点的子树的最大值,如果大于零,那么我们就把根通向这棵子树的边连接起来。

\(j\)\(i\)子树根节点的编号,有$f_i = \sum f_j \times [f_j > 0] $

关于正确性,可能会有问题:对于一棵子树而言,我们只考虑了这些向下的分支,并没有考虑向上父节点的这支“分支”,感觉不太对劲?

实际上,我们要明确我们这里求的是一个小范围内子问题的最优解,不是全局最优解。如果每个点都考虑所有的分支情况(包括向上找父亲的那个分支),那么所有的点都是在求全局最优解,这样就无法进行DP或者状态转移了, 问题也没有得到简化。

我们考虑所谓“向上”的分支,实际上就是上面“向下”的分支,所以这种情况显然是可以被覆盖到的。如果上面的向下伸的这个分支是断的,没有到达这个子树的根节点,那么这棵子树加上向上一段的分支最大也会是负的,显然单独的子树或者单独的上面那个点都是更优的,不会有贡献。

实际上,我们陷入这种思维泥潭的主要原因还是不清楚DP的逻辑——DP的局部最优解是为全局服务的,这个局部最优解是在某种定义下成立的,不代表全局最优,但是可以求出全局最优。就比如这道题里面的局部最优解就不包括向上的分支,它只考虑这一棵子树内的情况,这样保证了问题的规模从小到大,保证了其他可以DP的性质。

思考DP算法,某种意义上而言,是一种构建数学和逻辑的“自动机”的过程。

DP可以从经验出发,可以从DP性质出发, 也可以从问题本身的性质出发,三者相互联系,加上一些转化或者优化的技巧可以求解。

总结:树形DP的一种一般分析方法是有序化(有根树)后考虑子树上跟和子树的关系转移;可以从小规模子问题入手;定义一种可以转移的状态(意义),并确定初始值和转移方法;时刻清楚讨论的问题和环境是什么,比如在局部最优中讨论整体最优就是无太大意义的,因为DP中不需要考虑

一种步骤:转化、子问题、状态、转移方程、优化

要格外注意递归中的“回头找”和计算和的关系。在这里是,不能把判断vis放到开头,不但多递归一层,就会多计算一层和。

源码:


#include <bits/stdc++.h>

#define N (int)(16005)

using namespace std;

typedef long long LL;

LL a[N];

vector<int> e[N];

LL f[N];

LL ans;

bool vis[N];

void dfs(int p)
{
	ans = max(ans,f[p]);
	vis[p] = true;
	vis[p] = true;
	//cout << p << "\n";
	for(int i = 0;i < e[p].size();i++)
	{
		int q = e[p][i];
		if(vis[q]) continue;
		dfs(q);
		//cout << p << " " << q << " " << f[p] << " " << f[q] << "\n";
		if(f[q] > 0) f[p] += f[q];
		ans = max(ans,f[p]);
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	int n;
	cin >> n;
	memset(f,0x8f,sizeof(f));
	memset(vis,0,sizeof(vis));
	ans = -1e18;
	for(int i = 1;i <= n;i++)
	{
		cin >> a[i];
		f[i] = a[i];
	}
	for(int i = 1;i <= n-1;i++)
	{
		int x,y;
		cin >> x >> y;
		e[x].push_back(y);
		e[y].push_back(x);
	}
	dfs(1);
	cout << ans << "\n";
	return 0;
}

热门相关:恭喜你被逮捕了   神算大小姐   裙上之臣   万古至尊   锦庭娇