[算法总结] 树形dp 285. 没有上司的舞会

前言

现在感觉树形dp 其实就是多个链构成的dp而已

题目传送门

状态表示(该题)

f[u][0] 从以u为根的子树中选择的方案(并且不选U这个点的方案)

f[u][1] 所有从以u的子树中选并且选择U这个点的方案

所以状态计算 直接就出来了 就是选根就不选子,选子就不选根

code:

#include 
#include 
#include 

using namespace std;

const int N = 6010;

int n;
int h[N], e[N], ne[N], idx;
int happy[N];
int f[N][2];
bool has_fa[N];

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
} /// 用邻接表建树

void dfs(int u)
{
    f[u][1] = happy[u];
    ///因为 [u][0]是不选根节点 所以不用加

    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        
        dfs(j);

        f[u][1] += f[j][0]; ///选择根节点 那么其子节点都不选
        f[u][0] += max(f[j][0], f[j][1]); 
        ///不选根节点  那么就要考虑这个点是否要选因为 Happy有负数
    }
}

int main()
{
    scanf("%d", &n);

    for (int i = 1; i