蓝桥杯2015年第六届真题-生命之树

题目

题目链接

题解

树状DP。

基础树状DP题了。

首先先讲一下题目什么意思（起初，我就理解错了）

题目说在树上找一些点，这些点满足：在这些点中任取两个点a和b，都能够找到一条路径连通。

我这样一翻译是不是感觉清晰多了，其实就是找一个点集，保证点击任意两点可达，这就是在找个连通区域。

（最开始，我理解成了要找一条直径使得直径上的点价值加起来最大……）

dp[i][0/1]表示以i为根的子树不选取根节点i和选取根节点i构成连通区域的最大分数；（比较难以描述） dp[i][0]是不选根节点，意味着以i为根节点的树的那些不包含i的子树的最大分数为dp[i][0]，这个连通区域要么是i的左子树中，要么在右子树中，而每棵子树也包含两种状态，即含根与不含根，所以转移方程为：dp[i][0] = max(dp[i][0], dp[j][1], dp[j][0])，其中j为i的子节点。 dp[i][1]是选根节点，意味着这个连通区域一定要跨越i，当然可以i的某个子树中一个节点都不选，也可以选若干个，只要保证连通即可。遍历每个子结点j，如果想要与i构成连通区域，那么j节点必须被选上，要是不选j的话i节点根本没法与以j为根节点的子树部分相连通啊，当然，i也可以选择不与j的子树连通，对于这两种情况选个最大的得分加上，每个子节点都遍历完成，都加上了就算出了dp[i][1]。所以转移方程为：dp[i][1] += max (0, dp[j][1])

注意开LL。

代码

#include
using namespace std;
typedef long long LL;

const int N = 1e5+10;

int e[N u >> v, 
		add (u, v),
		add (v, u);

	dfs (1, 0);
	
	cout