C++树形DP（选与不选模型）

qq_43355454

167人浏览 · 2025-12-11 15:23:18

qq_43355454 · 2025-12-11 15:23:18 发布

树形DP 代码框架见下

#include <iostream>
#include <vector>
using namespace std;

#define type int
#define maxn 200010
#define inf 1000000000
int n;
// dp[i][0]代表以i为根节点的子树，且根节点不选最大（小）值（或者方案数）
// dp[i][1]代表以i为根节点的子树，且根节点  选最大（小）值（或者方案数）
type dp[maxn][2];
vector<int> child[maxn];

type TreeDPSample_InitVal(int u, int isChoose) {
    return isChoose;
}

type TreeDPSample_Opt(type curVal, bool isChoose, type ncVal, type cVal) {
    if (isChoose) {
        return curVal + min(ncVal, cVal);
    }
    return curVal + cVal;
}

void TreeDPSample_Init(int n) {
    for (int i = 0; i <= n; ++i) {
        dp[i][0] = dp[i][1] = inf;
    }
}

type TreeDPSample_DFS(int u, bool isChoose, int fat) {
    type& ans = dp[u][isChoose];
    if (ans != inf) {
        return ans;
    }
    ans = TreeDPSample_InitVal(u, isChoose);

    for (int i = 0; i < child[u].size(); ++i) {
        int v = child[u][i];
        if (v == fat) {
            continue;
        }
        type nc = TreeDPSample_DFS(v, false, u);
        type c = TreeDPSample_DFS(v, true, u);
        ans = TreeDPSample_Opt(ans, isChoose, nc, c);

    }
    return ans;
}

int main()
{
    cin >> n;
    TreeDPSample_Init(n);
    for (int i = 0; i < n - 1; ++i) {
        int x, y;
        cin >> x >> y;
        child[x].push_back(y);
        child[y].push_back(x);
    }
    type ans = min(
        TreeDPSample_DFS(1, true, 0),
    TreeDPSample_DFS(1, false, 0)
        );
    cout << ans << endl;
    // 请在此输入您的代码
    return 0;
}

代码练习 1 对应蓝桥云课生命之树

#include <iostream>
#include <vector>
using namespace std;

#define type long long
#define maxn 100010
#define inf -1000000000000000011
int n;
// dp[i][0]代表以i为根节点的子树，且根节点不选最大（小）值（或者方案数）
// dp[i][1]代表以i为根节点的子树，且根节点  选最大（小）值（或者方案数）
type dp[maxn][2];
vector<int> child[maxn];
type a[maxn];

type TreeDPSample_InitVal(int u, int isChoose) {
    return a[u] * isChoose;
}

type TreeDPSample_Opt(type curVal, bool isChoose, type ncVal, type cVal) {
    if (isChoose) {
        return curVal + max(ncVal, cVal);
    }
    return 0;
}

void TreeDPSample_Init(int n) {
    for (int i = 0; i <= n; ++i) {
        dp[i][0] = dp[i][1] = inf;
    }
}

type TreeDPSample_DFS(int u, bool isChoose, int fat) {
    type& ans = dp[u][isChoose];
    if (ans != inf) {
        return ans;
    }
    ans = TreeDPSample_InitVal(u, isChoose);

    for (int i = 0; i < child[u].size(); ++i) {
        int v = child[u][i];
        if (v == fat) {
            continue;
        }
        type nc = TreeDPSample_DFS(v, false, u);
        type c = TreeDPSample_DFS(v, true, u);
        ans = TreeDPSample_Opt(ans, isChoose, nc, c);

    }
    return ans;
}

int main()
{
    cin >> n;
    TreeDPSample_Init(n);
    for(int i=1; i <= n; ++i){
      cin >> a[i];
    }
    for (int i = 0; i < n - 1; ++i) {
        int x, y;
        cin >> x >> y;
        child[x].push_back(y);
        child[y].push_back(x);
    }
    type ans = inf;
    for(int i=1; i <= n; ++i){
      TreeDPSample_DFS(i, 0, 0);
      TreeDPSample_DFS(i, 1, 0);
      ans = max(ans, max(dp[i][0], dp[i][1]));
    }
    cout << ans << endl;
    // 请在此输入您的代码
    return 0;
}

代码练习 2 树的着色问题对应蓝桥云课代码见下

#include <iostream>
#include <vector>
using namespace std;

#define mod 1000000007
#define type long long
#define maxn 100010
#define inf 1000000000
int n;
// dp[i][0]代表以i为根节点的子树，且根节点不选最大（小）值（或者方案数）
// dp[i][1]代表以i为根节点的子树，且根节点  选最大（小）值（或者方案数）
type dp[maxn][2];
vector<int> child[maxn];
int a[maxn];

type TreeDPSample_InitVal(int u, int isChoose) {
    return 1;
}

type TreeDPSample_Opt(type curVal, bool isChoose, type ncVal, type cVal) {
    if (isChoose) {
        return curVal * ncVal % mod;
    }
    return curVal * (ncVal + cVal) % mod;
}

void TreeDPSample_Init(int n) {
    for (int i = 0; i <= n; ++i) {
        dp[i][0] = dp[i][1] = inf;
    }
}

type TreeDPSample_DFS(int u, bool isChoose, int fat) {
    type& ans = dp[u][isChoose];
    if (ans != inf) {
        return ans;
    }
    ans = TreeDPSample_InitVal(u, isChoose);

    for (int i = 0; i < child[u].size(); ++i) {
        int v = child[u][i];
        if (v == fat) {
            continue;
        }
        type nc = TreeDPSample_DFS(v, false, u);
        type c = TreeDPSample_DFS(v, true, u);
        ans = TreeDPSample_Opt(ans, isChoose, nc, c);

    }
    return ans;
}

int main()
{
    cin >> n;
    TreeDPSample_Init(n);
    for (int i = 0; i < n - 1; ++i) {
        int x, y;
        cin >> x >> y;
        child[x].push_back(y);
        child[y].push_back(x);
    }
    type ans = (
        TreeDPSample_DFS(1, true, 0) +
        TreeDPSample_DFS(1, false, 0)
        ) % mod;
    cout << ans << endl;
    // 请在此输入您的代码
    return 0;
}

代码练习 3 对应蓝桥云课没有上司的舞会代码见下

#include <iostream>
#include <vector>
using namespace std;

#define type int
#define maxn 5010
#define inf -1000000000
int n;
// dp[i][0]代表以i为根节点的子树，且根节点不选最大（小）值（或者方案数）
// dp[i][1]代表以i为根节点的子树，且根节点  选最大（小）值（或者方案数）
type dp[maxn][2];
vector<int> child[maxn];
int a[maxn];

type TreeDPSample_InitVal(int u, int isChoose) {
    return a[u] * isChoose;
}

type TreeDPSample_Opt(type curVal, bool isChoose, type ncVal, type cVal) {
    if (isChoose) {
        return curVal + ncVal;
    }
    return curVal + max(ncVal, cVal);
}

void TreeDPSample_Init(int n) {
    for (int i = 0; i <= n; ++i) {
        dp[i][0] = dp[i][1] = inf;
    }
}

type TreeDPSample_DFS(int u, bool isChoose, int fat) {
    type& ans = dp[u][isChoose];
    if (ans != inf) {
        return ans;
    }
    ans = TreeDPSample_InitVal(u, isChoose);

    for (int i = 0; i < child[u].size(); ++i) {
        int v = child[u][i];
        if (v == fat) {
            continue;
        }
        type nc = TreeDPSample_DFS(v, false, u);
        type c = TreeDPSample_DFS(v, true, u);
        ans = TreeDPSample_Opt(ans, isChoose, nc, c);

    }
    return ans;
}

int main()
{
    cin >> n;
    TreeDPSample_Init(n);
    for(int i=1; i <= n; ++i){
      cin >> a[i];
    }
    for (int i = 0; i < n - 1; ++i) {
        int x, y;
        cin >> x >> y;
        child[x].push_back(y);
        child[y].push_back(x);
    }
    type ans = max(
        TreeDPSample_DFS(1, true, 0),
    TreeDPSample_DFS(1, false, 0)
        );
    cout << ans << endl;
    // 请在此输入您的代码
    return 0;
}

AI Agent技术社区

Agent 垂直技术社区，欢迎活跃、内容共建。

更多推荐

Agent 实操入门 02：第一款工具怎么挑、怎么用 —— 以腾讯 WorkBuddy 为例

AI Agent技术社区

我用 Codex，给本地量化数据库搭了一套数据质检系统

AI Agent技术社区

Harness Engineering 完全解读：让 AI Agent 从跑偏到可控

《Harness Engineering：AI Agent可控化工程实践》摘要 Harness Engineering是2026年AI工程的关键范式，由Mitchell Hashimoto提出，核心是"人类掌舵，智能体执行"。该理念将AI模型视为"大脑"，通过构建约束系统（Harness）——包括格式规范、流程编排、工具白名单等前馈引导，以及自动化校验、评估