自动搬运

查看原文

来自洛谷，原作者为

	Mr_Eight H6_6Q sing.

搬运于2025-08-24 22:18:43，当前版本为作者最后更新于2020-04-18 19:21:48，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

很典型的一道树形DP

首先简化一下题目：每个人有 $x-$ $v_{i}$块钱（可为负）。要求出使所有人的钱数都 $≥0$。

$DP$状态确立

设 $dp_{i,j}$ 为在节点为 $i$ 的子树内进行 $j$ 次操作，使除 $i$ 号节点外，$i$ 的所有子节点的钱数都 $≥0$ 时（符合要求），$i$ 号节点最多能有的钱数（若为负数，则意为还需要父节点给自己的钱数）。

$DP$转移式

对于每一个节点，每添加一颗子树时，

$(1)$将子节点的钱向上运：

next[pos][j+k+1]=max(next[pos][j+k+1],dp[pos][j]+dp[c[pos][i]][k])

其中 $pos$ 是该节点， $c[pos][i]$ 表示正在添加的子树。

$(2)$当 $dp[c[pos][i]][k]$ $≥0$ 时，可以不将子节点的钱向上运：

if(dp[c[pos][i]][k]>=0){
	next[pos][k+j]=max(next[pos][k+j],dp[pos][j]);
}

附上丑陋的代码（仅删去头文件部分）

#define F(i,a,b) for(register int i=a,i##end=b;i<=i##end;++i)
using namespace std;
int read() {
	int x=0;
	bool fu=0;
	char ch=0;
	while(ch>'9'||ch<'0') {
		ch=getchar();
		if(ch=='-')fu=1;
	}
	while(ch<='9'&&ch>='0') x=(x*10+ch-48),ch=getchar();
	return fu?-x:x;
}
int n,t1,t2,x,v[2002],f[2002],dp[2002][2002],size[2002],next[2002][2002];
bool vis[2002];
vector<int>g[2002],c[2002];
void make_tree(int pos) {
	vis[pos]=1;
	if(g[pos].size()<=1 && pos!=1) {
		size[pos]=1;
		return;
	}
	size[pos]=1;
	F(i,0,g[pos].size()-1) {
		if(!vis[g[pos][i]]) {
			c[pos].push_back(g[pos][i]);
			f[g[pos][i]]=pos;
			make_tree(g[pos][i]);
			size[pos]+=size[g[pos][i]];
		}
	}
}
void DP(int pos) {
	int ssize=0;
	F(i,0,c[pos].size()-1) {
		DP(c[pos][i]);
	}
	F(i,0,c[pos].size()-1) {
		F(j,0,2001) {
			next[pos][j]=(-INT_MAX)/3;
		}
		F(j,0,ssize) {
			F(k,0,size[c[pos][i]]-1) {
				next[pos][j+k+1]=max(next[pos][j+k+1],dp[pos][j]+dp[c[pos][i]][k]);
				if(dp[c[pos][i]][k]>=0) {
					next[pos][k+j]=max(next[pos][k+j],dp[pos][j]);
				}
			}
		}
		F(j,0,2000) {
			dp[pos][j]=next[pos][j];
		}
		ssize+=size[c[pos][i]];
	}
}
int main() {
	memset(dp,-0x1f,sizeof(dp));
	cin>>n>>x;
	F(i,1,n) {
		v[i]=x-read();
		dp[i][0]=v[i];
	}
	F(i,2,n) {
		t1=read(),t2=read();
		g[t1].push_back(t2);
		g[t2].push_back(t1);
	}
	make_tree(1);//建树
	DP(1);//DP
	F(i,0,2000) {//输出答案
		if(dp[1][i]>=0) {
			cout<<i;
			return 0;
		}
	}
	return 0;
}

记得双击，么么哒（