洛谷 P1352 没有上司的舞会 树形DP板子

luogu传送门

题目描述：

某大学有n个职员，编号为1~n。

他们之间有从属关系，也就是说他们的关系就像一棵以校长为根的树，父结点就是子结点的直接上司。

现在有个周年庆宴会，宴会每邀请来一个职员都会增加一定的快乐指数 r​，但是呢，如果某个职员的直接上司来参加舞会了，那么这个职员就无论如何也不肯来参加舞会了。

所以，请你编程计算，邀请哪些职员可以使快乐指数最大，求最大的快乐指数。

 

一道树形DP的板子题。

状态转移方程看代码。

#include <bits/stdc++.h>

using namespace std;

#define N 100100

#define isdigit(c) ((c)>='0'&&(c)<='9')

inline int read(){

    int x = , s = ;

    char c = getchar();

    while(!isdigit(c)){

        if(c == '-')s = -;

        c = getchar();

    }

    while(isdigit(c)){

        x = (x << ) + (x << ) + (c ^ '');

        c = getchar();

    }

    return x * s;

}

struct node{

    int v;

    int next;

} t[N];

int f[N];

int happy[N];

bool vis[N];

int root = ;

int bian = ;

inline void add(int u, int v){

    t[++bian] = (node){v, f[u]};

    f[u] = bian;

    return ;

}

int dp[N][];

void dfs(int now){

    dp[now][] = ;

    dp[now][] = happy[now];

    for(int i = f[now]; i; i = t[i].next){

        int v = t[i].v;

        dfs(v);

        dp[now][] += max(dp[v][], dp[v][]);

        dp[now][] += dp[v][];

    }

}

int main(){

    int n = read();

    for(int i = ;i <= n; i++) happy[i] = read();

    for(int i = ;i < n; i++){

        int x = read(), y = read();

        add(y, x);

        vis[x] = ;

    }

    for(int i = ;i <= n; i++)

        if(!vis[i]){

            root = i;

            break;

        }

    dfs(root);

    printf("%d\n", max(dp[root][], dp[root][]));

}