树状dp(dfs)(一道挺基础的)

P1352 没有上司的舞会 

每个点都有两个状态（1/0），即选或者不选，如果选了，因此我们可以设置 dp[0][i]为点没选之后的最大值。 dp[i][1]设置为点选之后的最大值

转移方程：

dp[0][i]+=max(dp[1][son],dp[0][son]);

不去，那下属就可以想去就去。

dp[i][1]+=(dp[0][son])+r[i];

去了那下属就一定不能去。

以这两个状态同时计算，往下递推，然后程序自然递归回来；

#include<bits/stdc++.h>
using namespace std;
const int N = 6e3 + 10;
int r[N];//每个人自己的开心
int dp[2][N];
vector<int> ed[N];//用来储存树的，一个上司不止1下属，
bool son[N];//看看有没有上司的，用来寻找最根的节点，方便遍历
void dfs(int x){
    dp[1][x] = r[x];//先给每个人来的状态设自己为基础开心dp[i][1]+=(dp[0][son])+r[i];//因为后面遍历加直系下属，所以先把这个加一次的提前加好；
    for(auto y:ed[x]){
         dfs(y);
         dp[1][x] += max(0,dp[0][y]);
        dp[0][x] += max(0,max(dp[1][y],dp[0][y]));
 }
}

int main(){
     int n;cin >> n;
     for(int i = 1;i <= n;i++)
        cin >> r[i];
     for(int i = 1;i <= n - 1;i++){
         int x,y;cin >> x >> y;
         son[x] = 1;//有上司就标是儿子
         ed[y].push_back(x);
     }
     int root;
     for(int i = 1;i <= n;i++)//没有上司就是顶头上司，根
     if(!son[i]){
         root = i;
         dfs(i);
     break;
     }
    cout << max(dp[0][root],dp[1][root]);
      return 0;
}