315004 - 没有上司的舞会

题解byliuhaonan

背包型树形DP模板题目

f[0][i]表示不取i节点最大值 f[1][i]表示取i节点最大值

则f[0][i] = sum(max(f[1][son],f[0][son])) f[1][i] = sum(f[0][son])

最后答案是max(f[0][root],f[1][root])

#include <iostream>

#include <vector>
using namespace std;

int a[6010],f[2][6010]; //f[0][i]表示不取节点i最大值， f[1][i]表示取节点i最大值
vector tree[6010];
bool son[6010]; //检查某节点是不是别人的儿子，以此判断它是不是根节点

void DFS(int x) {

f[1][x] = a[x];
for(int i = 0;i < tree[x].size();i++) //遍历此节点的儿子 
{
	int s;
	s = tree[x][i]; //儿子节点 
	DFS(s); //搜索儿子 
	f[0][x] += max(f[0][s],f[1][s]); //转移 
	f[1][x] += f[0][s];
}
return;
}

int main() {

int n,i,j,root;
cin>>n;
for(i = 1;i <= n;i++) cin>>a[i];
for(i = 1;i < n;i++)
{
	int x,y;
	cin>>x>>y;
	tree[y].push_back(x); //建树 
	son[x] = true; //x是儿子 
}
for(i = 1;i <= n;i++) if(!son[i]) //如果不是儿子 
{
	root = i; //就是根 
	break;
}
DFS(root);
cout<<max(f[0][root],f[1][root]);
return 0;
}