anniversary party

本来以为是一道很简单的提，可以分分钟解决（实际上就是很简单）

然而一直报错，找半天，竟然要多组输入（还是太菜了）

所以每组需要先初始化，

这是一道树形DP的简单题，具体思路就是我选这个上司就不能选他的直属下级，如果不选这个上司，那么选不选他的直属下级要看rate怎么样

接下来放代码：

#include <iostream>
#include <vector>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N=6001;
int dp[N][2],father[N];//rate[N];
vector<int>tree[N];
int n;
void dfs(int fa){
dp[fa][0]=0;
//dp[fa][1]=rate[fa];
for(int i=0;i<tree[fa].size();i++){
int child=tree[fa][i];
dfs(child);
dp[fa][0]+=max(dp[child][0],dp[child][1]);
dp[fa][1]+=dp[child][0];
}
}
int main()
{
//while(~scnaf("%d",&n)){
while(cin>>n){
for(int i=1;i<=n;i++){
scanf("%d",&dp[i][1]);
tree[i].clear();
father[i]=0;
}
int x,y;
scanf("%d%d",&x,&y);
while(x&&y){
tree[y].push_back(x);
father[x]=y;
scanf("%d%d",&x,&y);
}
int t=1;
while(father[t])t=father[t];
/*
int ans=0;
for(int i=1;i<=n;i++){
if(!father[i]){
dfs(i);
ans+=max(dp[i][0],dp[i][1]);
}
}
cout << ans << endl;
*/
dfs(t);
cout << max(dp[t][0],dp[t][1]) << endl;
}
return 0;
}

巴特西

anniversary party_hdu1520

最新文章

热门文章