自动搬运

查看原文

来自洛谷，原作者为

	JK_LOVER 却顾所来径，苍苍横翠微。

搬运于2025-08-24 22:06:38，当前版本为作者最后更新于2020-07-20 21:50:54，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题意

给你一棵节点个数为 $n$ 的有根树，求出在所给时间内的 $ans$ 最大值。QWQ

分析

对于每一个节点来看

• 停在这个节点了。

• 去遍历子树了。

• 一系列操作之后，返回父亲了。

那么我们可以定义状态。 $dp[x][i][0/1]$ 对于节点 $x$ 考虑，使用了 大小为 $i$ 的时间。其中 $0$ 表示去遍历子树了， $1$ 表示停在这个节点了。 而返回父亲则可以用 $dp[x][i+1][1]$ 表示，因为再走一步就可以返回父亲。有如下转移方程：

分别表示：

• 儿子返回父亲，父亲停下。

• 父亲停下，去儿子子树。

• 儿子返回，去父亲子树。

时间复杂度为 $O(nm^2)$ 。

代码

#include<bits/stdc++.h>
using namespace std;
int read()
{
	int x=0,f=0;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')f=1;ch=getchar();}
	while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
	return f?-x:x;
}
const int N = 1100;
int dp[N][N][2],n,m,val[N];
vector<int> G[N];
void dfs(int x,int fa)
{
	for(int i = 0;i < G[x].size();i++)
	{
		int y = G[x].at(i);
		if(y == fa) continue;
		dfs(y,x);
		for(int j = m;j >= 0;j--)
		{
			for(int k = m;k >= 0;k--)
			{
				if(k + j + 2 <= m) 
				dp[x][j+k+2][0] = max(dp[x][j+k+2][0],dp[x][j][0]+dp[y][k][1]);
				dp[x][j+k+2][1] = max(dp[x][j+k+2][1],dp[x][j][1]+dp[y][k][1]);	
				if(k + j + 1 <= m)
				dp[x][j+k+1][0] = max(dp[x][j+k+1][0],dp[x][j][1]+dp[y][k][0]);
			}
		}
	}
	for(int i = m;i >= 1;i--)
	dp[x][i][1] = max(dp[x][i][1],dp[x][i-1][1]+val[x]),
	dp[x][i][0] = max(dp[x][i][0],dp[x][i-1][0]+val[x]);
//	for(int i = 1;i <= m;i++)
//	{
//		cout<<"x:: " <<x<<"   i:: "<<i<<"  dp::"<<dp[x][i][0]<<endl;
//	}
}
int main()
{
	n = read();m = read();
	for(int i = 1;i <= n;i++) val[i] = read();
	for(int i = 1;i < n;i++)
	{
		int a = read(),b = read();
		G[a].push_back(b);
		G[b].push_back(a);
	}
	dfs(1,0);
	cout<<dp[1][m][0]<<endl;
	return 0;
}