ARTICLE · 1105004
2026亚太信息学奥赛真题:树形DP选点解析
2026亚太信息学奥赛真题:树形DP选点解析
#include <bits/stdc++.h> using namespace std; int n; vector<int> w; vector<vector<int>> g; vector<vector<long long>> dp; void dfs(int u, int p) { dp[u][1] = w[u]; dp[u][0] = 0; for (int v : g[u]) { if (v == p) continue; // 不回到父节点 dfs(v, u); dp[u][1] += dp[v][0]; // 选 u，儿子必不选 dp[u][0] += max(dp[v][0], dp[v][1]); // 不选 u，儿子取较优 } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); if (!(cin >> n)) return 0; w.assign(n + 1, 0); for (int i = 1; i <= n; i++) cin >> w[i]; g.assign(n + 1, {}); for (int i = 0; i < n - 1; i++) { int u, v; cin >> u >> v; g[u].push_back(v); g[v].push_back(u); } dp.assign(n + 1, vector<long long>(2, 0)); dfs(1, 0); cout << max(dp[1][0], dp[1][1]) << " "; return 0; } import sys sys.setrecursionlimit(1000000) def solve(n, w, edges): g = [[] for _ in range(n + 1)] for u, v in edges: g[u].append(v); g[v].append(u) dp = [[0, 0] for _ in range(n + 1)] def dfs(u, p): dp[u][1] = w[u] dp[u][0] = 0 for v in g[u]: if v == p: continue dfs(v, u) dp[u][1] += dp[v][0] dp[u][0] += max(dp[v][0], dp[v][1]) dfs(1, 0) return max(dp[1][0], dp[1][1]) # 样例 n = 7 w = [0, 5, 1, 1, 5, 1, 1, 1] # 1-based，w[0] 占位 edges = [(1,2),(1,3),(2,4),(2,5),(3,6),(3,7)] print(solve(n, w, edges)) # -> 13 
2026亚太信息学奥赛真题：树形DP选点解析
🌳 赛前特训｜亚太信息学奥赛（APIO）向来以算法思维见长。今天用一道原创「真题」拆解树形动态规划——信奥里最常见、也最容易被忽视的一类树上问题。
一、题目背景
学校社团招新，共有 N 名成员，编号 1…N，组长是 1 号。成员之间有明确的上下级关系，整体构成一棵以 1 号为根的树（父子即直接上下级）。现在要选出一支「代表队」，规则只有一条：有直接上下级关系的两个人不能同时入选。请回答：
最多能选出多少人（最大独立集）？ 进阶：每人还有「号召值」 w[i]，求代表队号召值总和的最大值（最大权独立集）。
二、样例
输入：N=7，号召值 w=[5,1,1,5,1,1,1]（1 号到 7 号），边 (1,2)(1,3)(2,4)(2,5)(3,6)(3,7)。
输出：13（选 1、4、5、6、7 号，5+5+1+1+1=13，且互不相邻）。
三、树形DP思路拆解
树没有环，天然适合「自底向上」用 DFS 处理。对树上每个节点 u，我们只关心两件事：
dp[u][1]：u 入选时，以 u 为根的子树的最大收益； dp[u][0]：u 不入选时，以 u 为根的子树的最大收益。
状态转移：
u 入选 → 它的每个儿子 v都不能入选：dp[u][1] = w[u] + Σ dp[v][0]；u 不入选 → 每个儿子可选可不选，取较优者： dp[u][0] = Σ max(dp[v][0], dp[v][1])。
答案即 max(dp[根][0], dp[根][1])。整个过程每个节点只算一次，是经典的「树上后序 DP」。
四、C++ 参考代码
五、Python 参考代码
六、复杂度与边界
时间复杂度 O(N)，每个节点与每条边只访问一次；空间复杂度 O(N)（邻接表 + DP 数组）；边界：单点树答案为 w[1]；号召值累加用long long防溢出；递归深度大时 Python 需setrecursionlimit。
七、考点拆解（6 点）
- 树形结构建模
：把上下级关系建成无向树，避免成环； - 树上后序遍历
：先递归处理子树，再合并到父节点； - 状态设计
：用「选 / 不选」两个状态覆盖所有合法情况； - 无后效性
：子树的答案不依赖父节点选择，满足 DP 前提； - 长整型防溢出
：号召值累加用 long long； - 对数复杂度
：把指数级暴力（枚举所有子集）压到线性，正是树形 DP 的价值。
八、动手练一练
把树改成「1 连接 2、3、4，2 再连接 5、6」，号召值全设为 1，最多能选几个人？欢迎在评论区贴出你的运行结果，下期拆解「换根 DP」的进阶玩法。
📚 免费少儿编程资料（夸克网盘领取）
以下资料来自夸克网盘分享。个人号链接暂不支持直接点击，请长按或复制下方链接，打开夸克网盘 App / 网页粘贴即可保存：
1. 全国青少年信息素养大赛复赛集训题目Python&C++.docx https://pan.quark.cn/s/93995d3cb150 2. 2024信息素养-智能算法应用挑战赛-复赛初中组题目7月7日.pdf https://pan.quark.cn/s/da97b5dbf75d 3. Python背记手册.pdf https://pan.quark.cn/s/7568ae9ca92b 4. Python课程 https://pan.quark.cn/s/a94bf02d00c6 5. 2024信息素养大赛图形化复赛集训题答案3-9 https://pan.quark.cn/s/6ccab7ec3cbc 6. 2025年03月份电子学会考级真题 https://pan.quark.cn/s/4403c4228912 7. 2025全国青少年信息素养大赛赛项说明 https://pan.quark.cn/s/d9d0df4a9f29 8. 青少儿信息素养大赛编程资料 https://pan.quark.cn/s/4ab6bd83be8a
资料持续更新，关注本号第一时间获取新分享。