树形dp(2) P1352 没有上司的舞会

胡乱分析

这个题目就是相对简单了，我基本想到了8成的转移方程，但是还是无奈dfs功底有点差写不出来…..
转移方程就是当前选这个父亲节点或者不选这个父亲节点的问题，如果选这个父亲节点的话那么加上子节点不选的，不选那么加上子节点不选和选的最大值
也就是说
dp[p][0]+=max(dp[s][0],dp[s][1])
dp[p][1]+=dp[s][0]
其中p是父亲节点s是子节点0代表不选1代表选那么dfs即可

代码

#include <bits/stdc++.h>
using namespace std;
int num[6666],dp[6666][6],bk[6666];
vector<int> G[6666];
void dfs(int p)
{
  dp[p][0]=0;
  dp[p][1]=num[p];
  for(int i=0;i<G[p].size();i++)
  {
    dfs(G[p][i]);
    dp[p][0]+=max(dp[G[p][i]][0],dp[G[p][i]][1]);
    dp[p][1]+=dp[G[p][i]][0];
  }
}
int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int n,rt;
  cin>>n;
  for(int i=1;i<=n;i++)
  cin>>num[i];
  for(int i=1;i<=n-1;i++)
  {
    int st,ed;
    cin>>ed>>st;
    bk[ed]++;
    G[st].push_back(ed);
  }
  for(int i=1;i<=n;i++)
  if(!bk[i])
  {
    rt=i;
    break;
  }
  dfs(rt);
  cout<<max(dp[rt][0],dp[rt][1]);
}