树形DP入门

Acwing285 没有上司的舞会

// f[i][0]表示以i为根的子树中节点i不选时的最大快乐指数
// f[i][1]表示以i为根的子树中节点i选择时的最大快乐指数
// 那么转移方程就是：（v为i的子结点）
// f[i][0] += max(f[v][0],f[v][1]); 根节点不选，子结点可选可不选
// f[i][1] += f[v][0] 根节点选了，子结点只能不选

void dfs(u) {
    f[u][0] = 0;
    f[u][1] = w[u];
    for(int i = head[u]; ~i; i = nxt[i]) {
        int v = to[i];
        dfs(v);
        f[u][0] += max(f[v][0],f[v][1]);
        f[u][1] += f[u][0];
    }
}

int ans = max(f[root][0],f[root][1]);

最大子树和

P1122 最大子树和

// f[i][0] f[i][1] 含义与上相同
// 转移方程略有不同，因题意不太相同
// 需要寻找一个和最大的连通块

void dfs(int u) {
    vis[u] = true;
    f[u][0] = 0;
    f[u][1] = w[u];
    for(int i = head[u]; ~i; i = nxt[i]) {
        int v = to[i];
        if(vis[v]) continue;
        dfs(v);
        f[u][0] = max(f[u][0],max(f[[v][1],f[v][0]));
        if(f[v][1] > 0) f[u][1] += f[v][1];
    }
}

选课

Acwing286 选课

// 树形分组背包

// f[i][j] 表示以i为根的子树中选择j门课的最大学分

void dfs(int u) {
    f[u][1] = w[u]; // 初始化，只选一个的话，权重就是w[u]
    for(int i = head[u]; ~i; i = nxt[i]) {
        int v = to[i];
        dfs(v);
        for(int j = m; j >= 0; j--)
            for(int k = 0; k < j; k++) // 小于j是因为要给根节点留一个空间
                f[u][j] = max(f[u][j],f[u][j-k]+f[v][k]);
    }
}

二叉苹果树

Acwing1074 二叉苹果树
P2015 二叉苹果树

void dfs(int u) {
    vis[u] = true;
    for(int i = head[u]; ~i; i = nxt[i]) {
        int v = to[i];
        if(vis[v]) continue; // 防止回去，因为建的双向边
        f[v][1] = w[i]; // 初始化
        dfs(v);
        for(int j = m; j >= 0; j--)
            for(int k = 0; k < j; k++)
                f[u][j] = max(f[u][j], f[u][j-k]+f[v][k])
    }
}

m++; // 此题要求留下m条边，即m+1个点
dfs(1); // 随意选根节点，假设为1

有依赖的背包问题

Acwing10 有依赖的背包问题

void dfs(int u) {
    f[u][v[u]] = w[u];  // 初始化
    for(int i = head[u]; ~i; i = nxt[i]) {
        int e = to[i];
        dfs(e);
        for(int j = m; j >= 0; j--)
            for(int k = 0; k <= j-v[u]; k++) // 给根节点留个空间
                f[u][j] = max(f[u][j], f[u][j-k]+f[e][k])
    }
}