Part 4.4 树形动态规划

树形动态规划，即在树上进行的动态规划。

因为树的递归性质，树形动态规划一般都是递归求解的。

没有上司的舞会

题目描述

某大学有 $n$ 个职员，编号为 $1\ldots n$ 。

他们之间有从属关系，也就是说他们的关系就像一棵以校长为根的树，父结点就是子结点的直接上司。

现在有个周年庆宴会，宴会每邀请来一个职员都会增加一定的快乐指数 $r_i$ ，但是呢，如果某个职员的直接上司来参加舞会了，那么这个职员就无论如何也不肯来参加舞会了。

所以，请你编程计算，邀请哪些职员可以使快乐指数最大，求最大的快乐指数。

输入格式

输入的第一行是一个整数 $n$ 。

第 $2$ 到第 $(n + 1)$ 行，每行一个整数，第 $(i + 1)$ 行的整数表示 $i$ 号职员的快乐指数 $r_i$ 。

第 $(n + 2)$ 到第 $2 n$ 行，每行输入一对整数 $l, k$ ，代表 $k$ 是 $l$ 的直接上司。

输出格式

输出一行一个整数代表最大的快乐指数。

样例 #1

样例输入 #1

样例输出 #1

提示

数据规模与约定

对于 $100\%$ 的数据，保证 $1\leq n \leq 6 \times 10^3$ ， $\leq r_i\leq 127$ ， $\leq l, k \leq n$ ，且给出的关系一定是一棵树。

解题思路

dp[i][0/1]:以第i个节点为根节点的子树的最大快乐值，0表示不选这个节点，1表示选这个节点

dp[i][0]=sum(max(dp[k][0],dp[k][1])) (k为i的子节点的编号)
dp[i][1]=sum(dp[k][0])

代码实现

#include<iostream>
#include<vector>
using namespace std;
#define MAX_N 6000
int dp[MAX_N+5][5];
int val[MAX_N+5];
vector<int>son[MAX_N+5];
vector<int>fa[MAX_N+5];
void dfs(int now)
{
	dp[now][0]=0;
	dp[now][1]=val[now];
	for(auto i:son[now])
	{
		dfs(i);
		dp[now][1]+=dp[i][0];
		dp[now][0]+=max(dp[i][0],dp[i][1]);
	}
	return ;
}
int main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)cin>>val[i];
	for(int i=1,a,b;i<=n-1;i++)
	{
		cin>>a>>b;
		fa[a].push_back(b);
		son[b].push_back(a);
	}
	int root;
	for(int i=1;i<=n;i++)
	if(!fa[i].size())
	{
		root=i;
		break;
	}
	dfs(root);
	cout<<max(dp[root][1],dp[root][0]);
	return 0;
 }

[NOIP2003 提高组] 加分二叉树

题目描述

设一个 $n$ 个节点的二叉树 $\text{tree}$ 的中序遍历为 $(1,2,3,\ldots,n)$ ，其中数字 $1,2,3,\ldots,n$ 为节点编号。每个节点都有一个分数（均为正整数），记第 $i$ 个节点的分数为 $d_i$ ， $\text{tree}$ 及它的每个子树都有一个加分，任一棵子树 $\text{subtree}$ （也包含 $\text{tree}$ 本身）的加分计算方法如下：

$\text{subtree}$ 的左子树的加分 $\times$ $\text{subtree}$ 的右子树的加分 $+$ $\text{subtree}$ 的根的分数。

若某个子树为空，规定其加分为 $1$ ，叶子的加分就是叶节点本身的分数。不考虑它的空子树。

试求一棵符合中序遍历为 $(1,2,3,\ldots,n)$ 且加分最高的二叉树 $\text{tree}$ 。要求输出

$\text{tree}$ 的最高加分。
$\text{tree}$ 的前序遍历。

输入格式

第 $1$ 行 $1$ 个整数 $n$ ，为节点个数。

第 $2$ 行 $n$ 个用空格隔开的整数，为每个节点的分数

输出格式

第 $1$ 行 $1$ 个整数，为最高加分（$ Ans \le 4,000,000,000$）。

第 $2$ 行 $n$ 个用空格隔开的整数，为该树的前序遍历。

样例 #1

样例输入 #1

5
5 7 1 2 10

样例输出 #1

145
3 1 2 4 5

提示

数据规模与约定

对于全部的测试点，保证 $\leq n< 30$ ，节点的分数是小于 $100$ 的正整数，答案不超过 $\times 10^9$ 。

解题思路

本题也是树上问题，但是和前两道题不同的是本题按照中序遍历顺序给出了每个点的值，而前两题按照的是父子关系。中序遍历的顺序也就是dfs的顺序，也正因此本题不需要像前面个两道题一样进行dfs+记忆化，本题可以直接按照区间dp的思路来实现。
dp[i][j]表示区间i到j的最大分数
dp[i][j]=max(dp[i][j],dp[i][k-1]*dp[k+1][j]+dp[k][k])
如何输出前序的顺序？记录每一段区间的根节点，之后按照先序遍历输出每一段的根节点。

代码实现

#include<iostream>
using namespace std;
#define MAX_N 30
int dp[MAX_N+5][MAX_N+5];
int root[MAX_N+5][MAX_N+5];
int n;
void output(int l,int r)
{
	if(l>r)return ;
	int u=root[l][r];
	cout<<u<<" ";
	output(l,u-1);
	output(u+1,r);
	return ;
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)cin>>dp[i][i],root[i][i]=i;
	for(int i=0;i<=n;i++)dp[i+1][i]=1;
	for(int l=2;l<=n;l++)
	{
		for(int i=1;i<=n-l+1;i++)
		{
			int j=i+l-1;
			for(int k=i;k<=j;k++)
			{
				if(dp[i][j]<dp[i][k-1]*dp[k+1][j]+dp[k][k])
				{
					dp[i][j]=dp[i][k-1]*dp[k+1][j]+dp[k][k];
					root[i][j]=k;
				}
			}
		}
	}
	cout<<dp[1][n]<<endl;
	output(1,n);
	return 0;
 }

最大子树和

题目描述

小明对数学饱有兴趣，并且是个勤奋好学的学生，总是在课后留在教室向老师请教一些问题。一天他早晨骑车去上课，路上见到一个老伯正在修剪花花草草，顿时想到了一个有关修剪花卉的问题。于是当日课后，小明就向老师提出了这个问题：

一株奇怪的花卉，上面共连有 $N$ 朵花，共有 $N - 1$ 条枝干将花儿连在一起，并且未修剪时每朵花都不是孤立的。每朵花都有一个“美丽指数”，该数越大说明这朵花越漂亮，也有“美丽指数”为负数的，说明这朵花看着都让人恶心。所谓“修剪”，意为：去掉其中的一条枝条，这样一株花就成了两株，扔掉其中一株。经过一系列“修剪“之后，还剩下最后一株花（也可能是一朵）。老师的任务就是：通过一系列“修剪”（也可以什么“修剪”都不进行），使剩下的那株（那朵）花卉上所有花朵的“美丽指数”之和最大。

老师想了一会儿，给出了正解。小明见问题被轻易攻破，相当不爽，于是又拿来问你。

输入格式

第一行一个整数 $n\ (1\le N\le 16000)$ 。表示原始的那株花卉上共 $n$ 朵花。

第二行有 $n$ 个整数，第 $i$ 个整数表示第 $i$ 朵花的美丽指数。

接下来 $n - 1$ 行每行两个整数 $a, b$ ，表示存在一条连接第 $a$ 朵花和第 $b$ 朵花的枝条。

输出格式

一个数，表示一系列“修剪”之后所能得到的“美丽指数”之和的最大值。保证绝对值不超过 $2147483647$ 。

样例 #1

样例输入 #1

7
-1 -1 -1 1 1 1 0
1 4
2 5
3 6
4 7
5 7
6 7

样例输出 #1

提示

数据范围及约定

对于 $60\%$ 的数据，有 $1\le N\le 1000$ ；
对于 $100\%$ 的数据，有 $1\le N\le 16000$ 。

解题思路

dp[i]:以i为根的子树的最大魅力值。
dp[i]=a[i]+sum(max(0,dp[j]))
以i为根的子树的最大魅力值为节点i的魅力值与子树剪枝或不剪枝的最大魅力值得和。

代码实现

#include<iostream>
#include<vector>
using namespace std;
#define MAX_N 16000
int dp[MAX_N+5];
vector<int>son[MAX_N+5];
int n,ans=-2147483647;
void dfs(int now,int before)
{
	for(auto i:son[now])
	{
		if(i==before)continue;
		dfs(i,now);
		dp[now]+=max(0,dp[i]);
	}
	return ;
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)cin>>dp[i];
	for(int i=1,x,y;i<=n-1;i++)
	{
		cin>>x>>y;
		son[x].push_back(y);
		son[y].push_back(x);
	}
	dfs(1,0);
	for(int i=1;i<=n;i++)ans=max(ans,dp[i]);
	cout<<ans;
	return 0;
}

[CTSC1997] 选课

题目描述

在大学里每个学生，为了达到一定的学分，必须从很多课程里选择一些课程来学习，在课程里有些课程必须在某些课程之前学习，如高等数学总是在其它课程之前学习。现在有 $N$ 门功课，每门课有个学分，每门课有一门或没有直接先修课（若课程 a 是课程 b 的先修课即只有学完了课程 a，才能学习课程 b）。一个学生要从这些课程里选择 $M$ 门课程学习，问他能获得的最大学分是多少？

输入格式

第一行有两个整数 $N$ , $M$ 用空格隔开。( $\leq N \leq 300$ , $\leq M \leq 300$ )

接下来的 $N$ 行,第 $I + 1$ 行包含两个整数 $k_i $和 $s_i$ , $k_i$ 表示第I门课的直接先修课， $s_i$ 表示第I门课的学分。若 $k_i=0$ 表示没有直接先修课（ $\leq {k_i} \leq N$ , $\leq {s_i} \leq 20$ ）。

输出格式

只有一行，选 $M$ 门课程的最大得分。

样例 #1

样例输入 #1

样例输出 #1

解题思路

本题是树上背包问题。
dp[i][j][k]表示以第i个点为根节点，选择j个包含自己与子节点在内的j个点在选择数量为k的情况下的最大分数。

dp[i][j][k]=max(dp[i][j-1][k],dp[i][j-1][k-l]+dp[c][c_son_cnt][l])

l表示分给第j个节点的可选数量，c表示第j个孩子节点的编号，c_son_cnt表示孩子节点c的孩子数量。

代码实现

（直接按照状态转移方程翻译的版本）

#include<iostream>
#include<vector>
using namespace std;
#define MAX_N 300
int dp[MAX_N+5][MAX_N+5];
vector<int>fa[MAX_N+5];
vector<int>son[MAX_N+5];
int k[MAX_N+5];
int n,m;
void dfs(int now)
{
	dp[now][1]=k[now];
	for(auto i:son[now])
	{
		dfs(i);
		for(int j=m+1;j>=1;j--)
		{
			for(int l=0;l<j;l++)
			{
				dp[now][j]=max(dp[now][j],dp[i][l]+dp[now][j-l]);
			}
		}
	}
	return ;
}
int main()
{
	cin>>n>>m;
	for(int i=1,a,b;i<=n;i++)
	{
		cin>>a>>b;
		fa[i].push_back(a);
		son[a].push_back(i);
		k[i]=b;
	}
	int root=0;
	dfs(root);
	cout<<dp[0][m+1];
	return 0;
}

（空间优化版本）

#include<iostream>
#include<vector>
using namespace std;
#define MAX_N 300
int dp[MAX_N+5][MAX_N+5];
vector<int>fa[MAX_N+5];
vector<int>son[MAX_N+5];
int k[MAX_N+5];
int n,m;
void dfs(int now)
{
	dp[now][1]=k[now];
	for(auto i:son[now])
	{
		dfs(i);
		for(int j=m+1;j>=1;j--)
		{
			for(int l=0;l<j;l++)
			{
				dp[now][j]=max(dp[now][j],dp[i][l]+dp[now][j-l]);
			}
		}
	}
	return ;
}
int main()
{
	cin>>n>>m;
	for(int i=1,a,b;i<=n;i++)
	{
		cin>>a>>b;
		fa[i].push_back(a);
		son[a].push_back(i);
		k[i]=b;
	}
	int root=0;
	dfs(root);
	cout<<dp[0][m+1];
	return 0;
}

有线电视网

题目描述

某收费有线电视网计划转播一场重要的足球比赛。他们的转播网和用户终端构成一棵树状结构，这棵树的根结点位于足球比赛的现场，树叶为各个用户终端，其他中转站为该树的内部节点。

从转播站到转播站以及从转播站到所有用户终端的信号传输费用都是已知的，一场转播的总费用等于传输信号的费用总和。

现在每个用户都准备了一笔费用想观看这场精彩的足球比赛，有线电视网有权决定给哪些用户提供信号而不给哪些用户提供信号。

写一个程序找出一个方案使得有线电视网在不亏本的情况下使观看转播的用户尽可能多。

输入格式

输入文件的第一行包含两个用空格隔开的整数 $N$ 和 $M$ ，其中 $\le N \le 3000$ ， $\le M \le N-1$ ， $N$ 为整个有线电视网的结点总数， $M$ 为用户终端的数量。

第一个转播站即树的根结点编号为 $1$ ，其他的转播站编号为 $2$ 到 $N - M$ ，用户终端编号为 $N - M + 1$ 到 $N$ 。

接下来的 $N - M$ 行每行表示—个转播站的数据，第 $i + 1$ 行表示第 $i$ 个转播站的数据，其格式如下：

$\ \ A_1 \ \ C_1 \ \ A_2 \ \ C_2 \ \ \ldots \ \ A_k \ \ C_k$

$K$ 表示该转播站下接 $K$ 个结点（转播站或用户），每个结点对应一对整数 $A$ 与 $C$ ， $A$ 表示结点编号， $C$ 表示从当前转播站传输信号到结点 $A$ 的费用。最后一行依次表示所有用户为观看比赛而准备支付的钱数。单次传输成本和用户愿意交的费用均不超过 10。

输出格式

输出文件仅一行，包含一个整数，表示上述问题所要求的最大用户数。

样例 #1

样例输入 #1

样例输出 #1

提示

样例解释

如图所示，共有五个结点。结点 ① 为根结点，即现场直播站，② 为一个中转站，③④⑤ 为用户端，共 $M$ 个，编号从 $N - M + 1$ 到 $N$ ，他们为观看比赛分别准备的钱数为 $3$ 、 $4$ 、 $2$ 。

从结点 ① 可以传送信号到结点 ②，费用为 $2$ ；

也可以传送信号到结点 ⑤，费用为 $3$ （第二行数据所示）；

从结点 ② 可以传输信号到结点 ③，费用为 $2$ ；

也可传输信号到结点 ④，费用为 $3$ （第三行数据所示）。

如果要让所有用户（③④⑤）都能看上比赛，则信号传输的总费用为： $2 + 3 + 2 + 3 = 10$ ，大于用户愿意支付的总费用 $3 + 4 + 2 = 9$ ，有线电视网就亏本了，而只让 ③④ 两个用户看比赛就不亏本了。

解题思路

本题依然是背包问题。
dp[i][j][k]:表示以i为根节点得树选择前j个子孩子在服务用户为k得情况下的最大收益。
dp[i][j][k]=max(dp[i][j-1][k-l]+dp[c][c_cnt_son][l])

代码实现

#include<iostream>
#include<vector>
#include<cstring> 
using namespace std;
#define MAX_N 3000
int n,m;
vector<int>son[MAX_N+5];
int dp[MAX_N+5][MAX_N+5];
int val[MAX_N+5][MAX_N+5];
int cnt_p[MAX_N+5];
void dfs(int now)
{
	for(int i=1;i<=son[now].size();i++)
	{	
		int c=son[now][i-1];
		dfs(c);
		cnt_p[now]+=cnt_p[c];
		for(int k=cnt_p[now];k>=1;k--)
		{
			for(int l=1;l<=cnt_p[c]&&l<=k;l++)
			{
				dp[now][k]=max(dp[now][k],dp[now][k-l]+dp[c][l]-val[now][c]);
			}
		}
	}
}
int main()
{
	memset(dp,-0x3f,sizeof dp);
	cin>>n>>m;
	for(int i=1,k;i<=n-m;i++)
	{
		cin>>k;
		for(int j=1,a,b;j<=k;j++)
		{
			cin>>a>>b;
			son[i].push_back(a);
			val[i][a]=b;
		}
	}
	for(int i=1;i<=n;i++)dp[i][0]=0;	
	for(int i=n-m+1;i<=n;i++)
	{
		cin>>dp[i][1];
		cnt_p[i]=1;
	}
	dfs(1);
	for(int i=m;i>=0;i--)
	{
		if(dp[1][i]>=0)
		{
			cout<<i;
			break;
		}
	}
	return 0;
 }

[ZJOI2006] 三色二叉树

题目描述

一棵二叉树可以按照如下规则表示成一个由 $0$ 、 $1$ 、 $2$ 组成的字符序列，我们称之为“二叉树序列 $S$ ”：

$\begin{cases} 0& \text表示该树没有子节点\\ 1S_1& 表示该树有一个节点，S_1 为其子树的二叉树序列\\ 2S_1S_2& 表示该树由两个子节点，S_1 和 S_2 分别表示其两个子树的二叉树序列 \end{cases}$

例如，下图所表示的二叉树可以用二叉树序列 $S=\texttt{21200110}$ 来表示。

你的任务是要对一棵二叉树的节点进行染色。每个节点可以被染成红色、绿色或蓝色。并且，一个节点与其子节点的颜色必须不同，如果该节点有两个子节点，那么这两个子节点的颜色也必须不同。给定一颗二叉树的二叉树序列，请求出这棵树中最多和最少有多少个点能够被染成绿色。

输入格式

输入只有一行一个字符串 $s$ ，表示二叉树序列。

输出格式

输出只有一行，包含两个数，依次表示最多和最少有多少个点能够被染成绿色。

样例 #1

样例输入 #1

1122002010

样例输出 #1

5 2

提示

数据规模与约定

对于全部的测试点，保证 $\leq |s| \leq 5 \times 10^5$ ， $s$ 中只含字符 0 1 2。

解题思路

dp1[i][0/1]:表示以i为根节点的树所能取得的最大绿色节点数量。0表示节点i不为绿色，1表示节点i为绿色。
dp1[i][0]=max(dp1[k1][0]+dp1[k2][1],dp1[k1][1]+dp1[k2][0]);
dp1[i][1]=dp1[k1][0]+dp2[k2][0]; (节点i有2个子节点)
dp1[i][0]=max(dp1[k1][0],dp1[k1][1]);
dp1[i][1]=dp1[k1][0]; (节点i有1个子节点)

为什么dp数组数组第二维只需要设置0/1，而不需要设置0/1/2模拟题目中的三种颜色？因为红色和蓝色是等价的，具有对称性，也就是说一个点为蓝色或者红色其dp值是相等的，所以可以直接用0表示其为蓝色或者红色。

#include<iostream>
#include<string>
#include<vector>
using namespace std;
#define MAX_N 500000
int dp1[MAX_N+5][2];
int dp2[MAX_N+5][2];
vector<int>son[MAX_N+5];
string s;
int cnt=1;
void build()
{
	int now=cnt;
	for(int i=1;i<=s[now-1]-'0';i++)
	{
		son[now].push_back(++cnt);
		build();
	}
	return ;
}
void dfs(int now)
{
	int cnt_son=son[now].size();
	if(cnt_son==2)
	{
		dfs(son[now][0]);
		dfs(son[now][1]);
		dp1[now][0]=max(dp1[son[now][0]][1]+dp1[son[now][1]][0],dp1[son[now][1]][1]+dp1[son[now][0]][0]);
		dp1[now][1]=dp1[son[now][0]][0]+dp1[son[now][1]][0]+1;
		dp2[now][0]=min(dp2[son[now][0]][1]+dp2[son[now][1]][0],dp2[son[now][1]][1]+dp2[son[now][0]][0]);
		dp2[now][1]=dp2[son[now][0]][0]+dp2[son[now][1]][0]+1;
	}
	else if(cnt_son==1)
	{
		dfs(son[now][0]);
		dp1[now][0]=max(dp1[son[now][0]][0],dp1[son[now][0]][1]);
		dp1[now][1]=dp1[son[now][0]][0]+1;
		dp2[now][0]=min(dp2[son[now][0]][0],dp2[son[now][0]][1]);
		dp2[now][1]=dp2[son[now][0]][0]+1;
	}
	else{
		dp1[now][0]=dp2[now][0]=0;
		dp1[now][1]=dp2[now][1]=1;
	}
	return ;
}
int main()
{
	cin>>s;
	build();
	dfs(1);
	cout<<max(dp1[1][0],dp1[1][1])<<" ";
	cout<<min(dp2[1][0],dp2[1][1]);
	return 0;
}

[USACO12FEB] Nearby Cows G

题目描述

Farmer John has noticed that his cows often move between nearby fields. Taking this into account, he wants to plant enough grass in each of his fields not only for the cows situated initially in that field, but also for cows visiting from nearby fields.

Specifically, FJ’s farm consists of N fields (1 <= N <= 100,000), where some pairs of fields are connected with bi-directional trails (N-1 of them in total). FJ has designed the farm so that between any two fields i and j, there is a unique path made up of trails connecting between i and j. Field i is home to C(i) cows, although cows sometimes move to a different field by crossing up to K trails (1 <= K <= 20).

FJ wants to plant enough grass in each field i to feed the maximum number of cows, M(i), that could possibly end up in that field – that is, the number of cows that can potentially reach field i by following at most K trails. Given the structure of FJ’s farm and the value of C(i) for each field i, please help FJ compute M(i) for every field i.

给你一棵 $n$ 个点的树，点带权，对于每个节点求出距离它不超过 $k$ 的所有节点权值和 $m_i$ 。

输入格式

* Line 1: Two space-separated integers, N and K.

* Lines 2…N: Each line contains two space-separated integers, i and j (1 <= i,j <= N) indicating that fields i and j are directly connected by a trail.

* Lines N+1…2N: Line N+i contains the integer C(i). (0 <= C(i) <= 1000)

第一行两个正整数 $n, k$ 。
接下来 $n - 1$ 行，每行两个正整数 $u, v$ ，表示 $u, v$ 之间有一条边。
最后 $n$ 行，每行一个非负整数 $c_i$ ，表示点权。

输出格式

* Lines 1…N: Line i should contain the value of M(i).

输出 $n$ 行，第 $i$ 行一个整数表示 $m_i$ 。

样例 #1

样例输入 #1

样例输出 #1

提示

There are 6 fields, with trails connecting (5,1), (3,6), (2,4), (2,1), and (3,2). Field i has C(i) = i cows.

Field 1 has M(1) = 15 cows within a distance of 2 trails, etc.

【数据范围】
对于 $100\%$ 的数据： $\le n \le 10^5$ ， $\le k \le 20$ ， $\le c_i \le 1000$

解题思路

树形dp求以某个点作为根节点的最大值较为容易，但是本题要求距离某个点k距离内的权重总和，也就是需要考虑父节点之前的情况,本题的关键在于两次的dfs，第一次按照一般思路求出以某点为根节点在k范围内子节点的权重和，第二次再考虑父节点及之前节点的值。
dp1[i][j]：以i为根节点在j范围内子节点的权重和
dp1[i][j]=sum(dp1[c][j-1])+dp[i][0] （c为孩子节点的编号）
dp2[i][j]:与节点i距离范围为j的节点的权重和
dp2[i][j]=dp1[i][j]+dp2[f][j-1]-dp1[i][j-2] （f为父节点的编号）

代码实现

#include<iostream>
#include<vector>
using namespace std;
#define MAX_N 100000
#define MAX_K 20
int dp1[MAX_N+5][MAX_K+5];
int dp2[MAX_N+5][MAX_K+5];
vector<int>son[MAX_N+5];
int n,k;
void dfs1(int now,int fa)
{
	for(int i=1;i<=k;i++)dp1[now][i]=dp1[now][0];
	for(auto i:son[now])
	{
		if(i==fa)continue;
		dfs1(i,now);//递归放在前，先求子节点的dp1再求父节点 
		for(int c=1;c<=k;c++)
		{
			dp1[now][c]+=dp1[i][c-1];
		}	
	}
	return ;
}
void dfs2(int now,int fa)
{
	for(int i=0;i<=k;i++)dp2[now][i]+=dp1[now][i];
	for(auto i:son[now])
	{
		if(i==fa)continue;
		dp2[i][1]+=dp1[now][0];
		for(int c=2;c<=k;c++)
		{
			dp2[i][c]+=(dp2[now][c-1]-dp1[i][c-2]);
		}
		dfs2(i,now);//递归放在后，父节点的dp2已知，根据父节点求子节点 
	}
	return ;
}
int main()
{
	cin>>n>>k;
	for(int i=1,a,b;i<=n-1;i++)
	{
		cin>>a>>b;
		son[a].push_back(b);
		son[b].push_back(a);
	}
	for(int i=1;i<=n;i++)cin>>dp1[i][0];
	dfs1(1,0);
	dfs2(1,0);
	for(int i=1;i<=n;i++)cout<<dp2[i][k]<<endl;
	return 0;
}

[CQOI2017] 小Q的棋盘

题目描述

小 Q 正在设计一种棋类游戏。

在小 Q 设计的游戏中，棋子可以放在棋盘上的格点中。某些格点之间有连线，棋子只能在有连线的格点之间移动。整个棋盘上共有 $V$ 个格点，编号为 $0,1,2,\cdots, V- 1$ ，它们是连通的，也就是说棋子从任意格点出发，总能到达所有的格点。小 Q 在设计棋盘时，还保证棋子从一个格点移动到另外任一格点的路径是唯一的。

小 Q 现在想知道，当棋子从格点 $0$ 出发，移动 $N$ 步最多能经过多少格点。格点可以重复经过多次，但不重复计数。

输入格式

第一行包含2个正整数 $V, N$ ，其中 $V$ 表示格点总数， $N$ 表示移动步数。

接下来 $V - 1$ 行，每行两个数 $a_i,b_i$ ，表示编号为 $a_i,b_i$ 的两个格点之间有连线。

输出格式

输出一行一个整数，表示最多经过的格点数量。

样例 #1

样例输入 #1

样例输出 #1

样例 #2

样例输入 #2

样例输出 #2

提示

【输入输出样例 1 说明】

从格点 $0$ 出发移动 $2$ 步。经过 $0, 1, 2$ 这 $3$ 个格点。

【输入输出样例 2 说明】

一种可行的移动路径为 $\to 1 \to 3 \to 5 \to 3 \to 7$ ，经过 $0, 1, 3, 5, 7$ 这 $5$ 个格点。

【数据规模与约定】

对于 $100\%$ 的测试点， $1\le N,V ≤ 100$ ， $0 ≤a_i,b_i< V$ 。

解题思路

dp[0/1][i][j][k]:以i为根节点对于包含节点i与子节点在内的j个节点走k步所经过的最多点的数量。其中0表示不用回到节点i，1表示要回到节点i。
dp[0][i][j][k]=max
(dp[0][i][j-1][k],dp[0][i][j-1][k-l]+dp[1][c][c_cnt_son][l-2],dp[1][i][j-1][k-l]+dp[0][c][c_cnt_son][l-1])

dp[1][i][j][k]=max(dp[1][i][j-1][k-l]+dp[1][c][c_cnt_son][l])

dp[1][c][c_cnt_son][l-2]处为什么是l-2？因为c是i的一个子节点，要想走一个来回还得多加2。
dp[0][c][c_cnt_son][l-1]处为什么是l-1？不需要走来回，只需要从节点i到达节点c，所以只加1。
注：上面的式子为了便于理解没有省去j这一维度，程序实现时会做空间优化。

代码实现

#include<iostream>
#include<vector>
using namespace std;
#define MAX_N 100
int dp[2][MAX_N+5][MAX_N+5];
vector<int>son[MAX_N+5];
int v,n;
void dfs(int now,int fa)
{
	for(int i=1;i<=son[now].size();i++)
	{
		int c=son[now][i-1];
		if(c==fa)continue;
		dfs(c,now);
		dp[0][now][1]=2;
		for(int k=n;k>=2;k--)
		{
			for(int l=1;l<=k;l++)
			{
				int temp;
				if(l==1)temp=dp[0][c][l-1]+dp[1][now][k-l];
				else temp=max(dp[0][now][k-l]+dp[1][c][l-2],dp[0][c][l-1]+dp[1][now][k-l]);
				dp[0][now][k]=max(dp[0][now][k],temp);
				if(k%2==1)continue;
				if(l>1)dp[1][now][k]=max(dp[1][now][k],dp[1][now][k-l]+dp[1][c][l-2]);
			}
		}
	}
	return ;
}
int main()
{
	cin>>v>>n;
	for(int i=1,a,b;i<=v-1;i++)
	{
		cin>>a>>b;
		son[a].push_back(b);
		son[b].push_back(a);
	}
	for(int i=0;i<v;i++)dp[0][i][0]=dp[1][i][0]=1;
	dfs(0,0);
	cout<<dp[0][0][n];
	return 0;
 }