我又回来惹！

这次发的还是dp（逃

众所周知，dp分类极为广泛，最基础的有背包dp，线性dp，然后就是dp与各种算法的结合，例如与图论结合的DAG上的dp以及树性dp，与倍增结合的倍增dp，与位运算结合的状压dp...
这次我要发惹就是树性dp的一道板子题“没有上司的舞会”

首先，我们来明确一下树形dp的定义。树形dp分为树形以及dp两方面，简单来说即为在树上跑dp，dp最重要的几大性质之一就是dp一般都可以分为若干个阶段，而在树形图上设计dp就较为简单，我们一般都以节点从深到浅（子树从小到大）的顺序作为dp的‘阶段’，又由于树形dp由深入浅的性质，我们一般用深搜来完成dp的状态转移。

以上就是树形dp的大致定义惹，下面讲一下树形dp的解题思路：
首先，我们要观察题面，确定题面同时符合树形和dp的性质，确定后我们先建一个树形图，然后根据题意写出本题的状态转移方程，最后就是把代码写出来，如果是在比赛可以再手打一个暴力进行对拍，要不然就直接交上去，我在这里预祝大家ac（逃

然后我们就该开始这次的重点惹，没有上司的舞会就是一道极为经典的树形dp。
首先，根据我们前面说的，我们将职员编号看作dp状态的一维，但很明显，一维是不够的，再看题目，我们发现有一个限制条件：“不过，没有职员愿意和直接上司一起参会。”
根据这个限制，我们可以很轻松的得出dp状态的第二维为根节点是否参加，我们用0和1来表示

此时我们设f(x,0)表示x不参加舞会，那么就可以从以x为根的子树中邀请一部分职员参加：

同样的，我们设f(x,1)表示x参加，那么所有s都无法参加，那么：

(我们设x为当前节点，s为x的所有直接子节点,而son(x)则为x的子节点的集合)

这样，本题的状态转移方程就求出来了，最后还要注意一点，由于本题输入的是一个有根树，所以我们还要先搜一遍找到校长（即根节点），而作为根节点，dp目标为max(f(root,0),f(root,1));

本题时间复杂度为O(N),可以轻松跑过6000.

my code

#include <bits/stdc++.h>
#define re() read ()

const int N = 6010;
using namespace std;

inline int read () {
    int f = 1, x = 0; char ch = getchar ();
    while (ch < '0' || ch > '9') {
        if (ch == '-') {
            f = -1;
        }
        ch = getchar ();
    }
    while (ch >= '0' && ch <= '9') {
        x = (x << 3) + (x << 1) + ch - '0';
        ch = getchar ();
    }
    return x * f;
}

vector<int>fa[N];

int root;
int n, happy[N], f[N][2];
bool head[N];

void dfs (int x) {
    f[x][0] = 0;
    f[x][1] = happy[x];
    for (int i = 0; i < fa[x].size(); i++) {
        int y = fa[x][i];
        dfs (y);
        f[x][0] += max (f[y][0], f[y][1]);
        f[x][1] += f[y][0];
    }
}

int main () {
    n = re();
    for (int i = 1; i <= n; i++) {
        happy[i] = re(); 
    }
    for (int i = 1; i <= n-1; i++) {
        int son, father;
        son = re(), father = re();
        head[son] = 1;
        fa[father].push_back(son);
    }
    for (int i = 1; i <= n; i++) {
        if (!head[i]) {
            root = i;
            break;
        }
    }
    dfs (root);
    cout << max (f[root][0], f[root][1]) << endl;
    return 0;
}