树形dp

树形 DP，即在树上进行的 DP。由于树固有的递归性质，树形 DP 一般都是递归进行的。
经典例题：没有上司的舞会。
https://www.acwing.com/activity/content/problem/content/1012/
状态设定：
dp[u][2]//0表示不选该点，1表示选该节点的快乐指数。
代码：

#include<bits/stdc++.h>
using namespace std;
const int N =6005;
vector<vector<int>>tree(N,vector<int>());
int happy[N];
int n;
bool vis[N];
int dp[N][2];//0表示不选该点，1表示选该节点
void dfs(int u)//递归求解
{
    dp[u][1] = happy[u];//选该节点，那么dp[u][1]等于该快乐值
    for(int&v:tree[u])//遍历所有孩子
    {
        dfs(v);//递归搜索
        dp[u][0] +=max(dp[v][0],dp[v][1]);//状态转移，当不选该节点时，最大快乐值为选择或不选该孩子节点的最大值。
        dp[u][1] += dp[v][0];//当选择该点时，不能选孩子节点，所有快乐值为dp[v][0]。
    }
}
int main(void)
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>happy[i];//输入节点值
    }
    int l,k;
    for(int i=1;i<=n-1;i++)//建树
    {
        cin>>l>>k;
        tree[k].push_back(l);
        vis[l] =true;
    }
    int root = 1;
    while(vis[root])//找root节点
    {
        root++;
    }
    dfs(root);
    cout<<max(dp[root][0],dp[root][1])<<endl;//最大值为选择根节点与不选择根节点当中的最大值。
    
    
}