树上最大权匹配入门：P3408恋爱树形DP详解

继续打卡信奥刷题。今天说的这道题是洛谷的 P3408 恋爱也是我最近在树形DP专题里卡得最狠的一道。题目名字看着轻松实际上不是读完题面就能套模板的题我前后WA了四发才过。如果你在准备CSP-S或者NOIP提高组这道题很适合作为“树上最大权匹配”的入门题做一遍它不考什么高冷数据结构真正难的是状态定义以及把“每个人最多恋爱一次”这个条件翻译成DP数组。我下面按自己AC的这版题面来讲给一棵 n 个点的树每条边有一个权值表示两个人之间的好感度。要求选出若干条边作为“恋爱关系”任意两条被选边不能共享端点问选出的边权和最大是多少。数据规模我按 n ≤ 1e5、边权 ≤ 1e9 来写代码如果你拿到的版本范围不同核心思路完全一样。1. 先把题面剥开P3408 恋爱本质上是一道树上最大权匹配1.1 题面故事背后的模型“恋爱关系”这个包装很容易让人想歪比如去考虑关系能不能交叉、人物顺序合不合理。真要动笔之前把它翻译成离散结构每个点是一个人只能出现在一段关系里每条边是可能发生的恋爱关系带一个好感度权值选边时任意两条选中的边不能有公共端点。这不就是经典的树上最大权匹配吗也叫最大权独立边集。在一棵树上选出若干条互不相邻的边让边权和最大。匹配是图论里的基础概念但放到树上之后很多习惯做“点权树形DP”的人会突然不顺手因为点权和边权的转移逻辑完全不同。我第一次做这题时第一反应是仿照“没有上司的舞会”写状态用一个点选或不选来表示。结果在样例上能过一到构造数据就WA。原因很简单“没有上司的舞会”限制的是相邻点不能同时选是点维度的约束而 P3408 限制的是边不能共用端点是边维度的约束。两者的父子关系表达方式不一样不能硬套。1.2 为什么不能用贪心一个三点星形反例就够树上有大量美好性质但“按边权从大到小选边”这件事并不成立。很多人看到“选若干条边、每条边有权值”会下意识想到活动安排问题里的贪心先按结束时间排序能选就选。树上匹配不行因为一条边占用了两个端点可能会封锁住旁边好几条更高性价比的边。举一个最简单的反例。一个星形树中心是 1 号点三个叶子分别是 2、3、4边权分别是(1, 2)8(1, 3)7(1, 4)7如果贪心先选最大边 (1, 2)总权值是 8。但此时 1 号点已经被占用剩下两条边都不能选。最优解其实是选 (1, 3) 和 (1, 4)总权值是 14。贪心输得很彻底。这个反例说明一个点到底“空闲”还是“已占用”会直接影响整棵子树的决策所以不能只盯着当前边权最大的边。必须把“当前点是否空闲”作为一个状态让每个子树在内部决策完后把对这个点的占用情况告诉父节点。这就是树形DP要解决的问题。2. 状态定义和转移方程从“每个人只能谈一次”推导出来2.1 两个状态分别代表什么做树形DP第一步不是写代码而是把状态含义写到草稿纸上。P3408 我给每个点开两个状态dp[u][0]处理完 u 的子树u 没有和任何子节点配对此时 u 是空闲的可以继续和父节点配对。 dp[u][1]处理完 u 的子树u 已经和某个子节点配对因此 u 不能再和父节点配对。注意这里的“配对”指的是选中了以 u 为一端的一条树边作为答案边。这个定义有一个很重要的作用父节点想知道 u 能不能和自己配对只需要看 dp[u][0]。因为 dp[u][0] 强制 u 空闲虽然可能不是 u 子树里的最优全局解但它是“允许 u 留给父节点”这个约束下的最优解。叶子节点没有孩子所以dp[leaf][0] 0 dp[leaf][1] -INF叶子不能和子节点配对1 状态不存在。这里要把负无穷设成一个足够小但不溢出的值我习惯用-(1LL 60)不要直接用LLONG_MIN否则后面一加就可能溢出成负数或未定义结果。2.2 转移方程的完整推导过程以 u 为根的子树遍历每个孩子 v。先不看边 (u, v) 选不选v 自己子树里的最优值是max(dp[v][0], dp[v][1])如果 u 和 v 之间的边不选那么 v 的子树自由发挥对 u 的贡献就是上面这个 max。如果 u 和 v 之间的边选中就有一个前提条件v 必须处于空闲状态因为 v 已经被 u “占用”了不能再和孩子配对。所以这时 v 对整棵树的贡献不是自由发挥值而是w(u, v) dp[v][0]注意这里必须用 dp[v][0]不能用 max(dp[v][0], dp[v][1])。我第一次就是在这里栽的选边时用了 max导致一条链上连续选了两条边答案虚高。现在考虑所有孩子。假设 u 暂时不和任何孩子配对那子树总贡献是sum Σ max(dp[v][0], dp[v][1])如果 u 想和某个孩子 v 配对整体收益相对于 sum 的变化是w(u, v) dp[v][0] - max(dp[v][0], dp[v][1])u 只能选一个孩子配对所以取这个差值最大的孩子。于是dp[u][0] sum dp[u][1] sum max( w(u, v) dp[v][0] - max(dp[v][0], dp[v][1]) )这个转移的本质是先把所有孩子的自由最优解加起来然后看把某一个孩子从“自由发挥”改成“强制空闲并连到 u”能带来多少增益选增益最大的那一个。如果所有增益都是负数dp[u][1] 会比 dp[u][0] 小但这并不影响最终答案因为最后答案取的是两个状态的最大值。根节点没有父节点所以最终答案是max(dp[root][0], dp[root][1])2.3 一个容易忽略的边界单点树n 1 时没有边答案显然是 0。这时候 dp[1][0] 0dp[1][1] sum best -INF因为 1 号点没有孩子。取 max 后输出 0逻辑是对的。但如果你在写代码时把 best 初始化为 0而不是 -INF问题就出现了单点情况下 dp[u][1] 会被算成 0似乎答案也对。可一旦这个 u 有父节点父节点在计算“u 是否空闲”时会把 dp[u][0] 和 dp[u][1] 做 max如果你的 dp[u][1] 被错误地填成了 0父节点可能误以为 u 可以白送一个匹配状态后面的状态就全乱了。所以叶子节点的 1 状态一定要是负无穷除非你非常清楚自己在干什么。3. C实现细节邻接表、递归风险与迭代后序遍历3.1 邻接表选型vector 还是链式前向星写树上DP时邻接表有两种常见写法vectorpairint,int g[N]或者链式前向星。数据量不大时 vector 写起来确实快代码也短。但 P3408 这类树的题目如果 n 到 1e5 甚至 1e6vector 每个节点都要动态分配内存局部性也不如数组连续存储。我一般直接用链式前向星题目出到大数据也不会慌。#include bits/stdc.h using namespace std; using ll long long; const int N 100005; const ll NEG -(1LL 60); struct Edge { int to, w, next; } e[N 1]; int head[N], tot 1; ll dp[N][2]; void addEdge(int u, int v, int w) { e[tot] {v, w, head[u]}; head[u] tot; e[tot] {u, w, head[v]}; head[v] tot; }这里tot从 1 开始0 作为空边。遍历时用for (int i head[u]; i; i e[i].next)。这个约定要和 head 数组初始化为 0 配套千万不要一会儿用 -1一会儿用 0。3.2 递归写法简洁但有爆栈风险递归写法非常直白方便理解。核心函数长这样void dfs(int u, int fa) { ll sum 0; ll best NEG; for (int i head[u]; i; i e[i].next) { int v e[i].to; if (v fa) continue; dfs(v, u); ll choose max(dp[v][0], dp[v][1]); sum choose; best max(best, (ll)e[i].w dp[v][0] - choose); } dp[u][0] sum; dp[u][1] sum best; }主函数先读入 n再读 n-1 条边从 1 号点开始 dfsint main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; for (int i 1; i n; i) { int u, v, w; cin u v w; addEdge(u, v, w); } dfs(1, 0); cout max(dp[1][0], dp[1][1]) \n; return 0; }如果题目给的是有根树直接把给定根节点传进 dfs 同样成立。无根树任意取 1 号点当根即可因为树上最大匹配不依赖根的位置。但递归有个隐患当树退化成一条链时递归深度是 n。n 1e5 时在部分评测环境下已经可能栈溢出n 1e6 时基本必炸。应对办法是写迭代后序遍历。3.3 迭代后序遍历一条链也不怕迭代的思路很简单先用栈做一次 DFS记录节点的访问顺序然后按照访问顺序的逆序来处理每个节点。因为树形DP里子节点的 dp 值必须先于父节点算好逆序访问正好满足这个依赖。int parent[N], order[N]; void buildOrder(int root) { int cnt 0; stackint st; st.push(root); parent[root] 0; while (!st.empty()) { int u st.top(); st.pop(); order[cnt] u; for (int i head[u]; i; i e[i].next) { int v e[i].to; if (v parent[u]) continue; parent[v] u; st.push(v); } } }访问顺序建好之后倒着遍历 order 数组做 DPbuildOrder(1); for (int idx n; idx 1; idx--) { int u order[idx]; ll sum 0; ll best NEG; for (int j head[u]; j; j e[j].next) { int v e[j].to; if (v parent[u]) continue; ll choose max(dp[v][0], dp[v][1]); sum choose; best max(best, (ll)e[j].w dp[v][0] - choose); } dp[u][0] sum; dp[u][1] sum best; }注意这里的树是无向树所以只需要跳过父节点。如果你题目给的树可能不是一棵树那就要额外用 visited 数组防环但 P3408 明确是树不用多此一举。用 stack 而不是 queue 来求 order 没有问题因为我们需要的是父子关系访问顺序本身不影响逆序 DP 的正确性。3.4 数据范围和读入优化边权如果达到 1e9n 1e5答案上限能到 1e14用 int 存必炸。所以我所有累加变量都用了long long转移里也把边权强转成ll再算。best max(best, (ll)e[j].w dp[v][0] - choose);这里如果漏了(ll)e[j].w dp[v][0]先按 int 算可能会溢出成负数然后 WA 得莫名其妙。读入层面n 到 1e5 时ios::sync_with_stdio(false); cin.tie(nullptr);足够。n 到 1e6 时我建议自己写一个快速读入函数或者用fread批量读否则 cin 哪怕关了同步也可能被卡常。这道题主要考 DP但竞赛里常因为输入慢而超时属于很冤的丢分。4. 样例过了却WA三个最常见的翻车点4.1 选边 (u, v) 时用错了孩子的状态我在 2.2 节强调过要选边 (u, v)必须让 v 处于空闲状态所以贡献是w(u, v) dp[v][0]。很多人写成best max(best, (ll)e[j].w choose - choose);甚至有人直接写成w。这等于默认“不管 v 有没有匹配孩子都可以再连 u”。如果 v 的子树里已经选了 (v, x)那么边 (u, v) 和 (v, x) 就共用了 v违反了“每个人只能谈一次”。我第一次WA的构造数据很简单根是 12 是 1 的孩子3 是 2 的孩子边权分别为 (1,2)1(2,3)100。正确答案是选 (2,3)得 100。如果用错状态计算 1 的 dp[1][1] 时会把 (1,2) 也算进去得到 101直接多算一条非法边。这个反例价值很大因为它不只影响最终答案还会让你对拍时看不出规律。建议在代码里刻意把这个位置标出来每次做完树形DP都检查一遍选父边时孩子用的到底是dp[v][0]还是max(dp[v][0], dp[v][1])。4.2 边表 head 初始化的约定不自洽链式前向星有两种常见写法head 初始化为 0tot 从 1 开始用for (int i head[u]; i; i e[i].next)遍历head 初始化为 -1tot 从 0 开始用for (int i head[u]; i ! -1; i e[i].next)遍历。这两种写法本身都正确但混在一起就会出问题。最典型的是 head 初始化为 -1却用了for (int i head[u]; i; i e[i].next)此时 i -1 条件为真代码会去访问 e[-1]结果不可预知。样例可能因为数据规模小没触发但随机数据一上来就RE或WA。我在本地调试时习惯在主函数开头统一初始化memset(head, 0, sizeof(head)); tot 1;如果有多个测试点每次都要重新初始化否则上一组数据的边还挂在 head 链上遍历时会把旧边也访问到dp 值全乱。4.3 溢出和“多组数据不清空”这类树形DP题常见的坑之一是把边权累加结果放进 int。你单独看一条边都知道不会超 int但 n-1 条边加在一起很可能超过 2^31。除了用 long long还要注意这类题如果有多个样例输入dp 数组不一定每次都要 memset因为 dfs 会重新覆盖所有节点的 dp 值但 head 数组必须清空tot 必须复位这是最容易漏的。另外best的初始值我建议写成NEG而不是某一个很大的正数。如果给一个正大数叶子节点会被错误地认为“有孩子可以匹配”dp[u][1] 会被填成一个不存在的非法值后面所有 max 都可能选到它。用负无穷至少能保证非法状态不会胜出。4.4 用对拍快速验证状态转移对于这种状态定义容易出错的题我强烈建议写一个暴力程序对拍。n 很小时可以枚举所有边的选/不选组合再检查是否有点被选了两次复杂度 O(2^(n-1))完全够用。思路如下// bf.cpp: n 12 的暴力 ll ans 0; for (int mask 0; mask (1 (n - 1)); mask) { vectorint cnt(n 1, 0); ll sum 0; bool ok true; for (int i 0; i n - 1; i) { if ((mask i) 1) { int u edges[i].u, v edges[i].v; cnt[u]; cnt[v]; sum edges[i].w; if (cnt[u] 1 || cnt[v] 1) { ok false; break; } } } if (ok) ans max(ans, sum); } cout ans \n;再写一个随机生成脚本每次生成 n ≤ 10 的树边权随机。然后用 bash 循环对拍for i in $(seq 1 1000); do python3 gen.py in.txt ./std in.txt out.txt ./bf in.txt ans.txt diff out.txt ans.txt || break done一旦出现 diff把 in.txt 留下来人工推一遍小数据基本一眼就能看出是选边时状态用错还是边界初始化有问题。我刷这题时靠这个流程十分钟就定位到了 4.1 那个错误比自己盯着代码干想高效得多。5. 从 P3408 往外走这类树上配对题还能怎么变5.1 和经典树形DP题的关系P3408 不是孤例。树形DP里有几道题外观相似状态却完全不同放在一起对比会非常清晰题目模型状态含义P1352 没有上司的舞会点权相邻点不能同时选dp[u][0/1] 表示 u 是否参加P2016 战略游戏点权选最少点覆盖所有边dp[u][0/1] 表示 u 是否驻守P3408 恋爱边权选边且边不共享端点dp[u][0/1] 表示 u 是否空闲这三道题的核心都是“相邻关系不能同时取”但一个限制点、一个限制边转移方程就差在这里。如果你能把这三种模型的状态定义和转移都写顺手树上DP这块的基本功就算扎实了。5.2 变式方向基环树、方案输出和计数P3408 的思维还能迁移到几个方向基环树最大权匹配先找环断掉一条环边枚举这条边选或不选分别跑两次树形DP取最大值。核心还是这个“空闲/占用”状态。输出方案转移时记录每个点选了哪个孩子以及每个孩子处于哪个状态最后按路径回溯。这时候状态语义就必须非常严格不能写dp[u][1] dp[u][0]之类的偷懒写法。边权为 1 的最大匹配数量把边权全设成 1答案就是树上最大匹配的边数。状态转移里的 best 就会变成判断“是否有一个孩子选择连边能带来 1 的增益”。我在做这些变式时有一个统一心得先问自己“父节点如果需要连向当前点当前点必须是哪种状态”再写转移。只要回答清楚这个问题代码基本不会有大方向错误。5.3 后续刷题建议如果你刚把 P3408 弄懂我建议按这个顺序往下刷先回头做 P1352 没有上司的舞会找找点权和边权的区别再做 P2016 战略游戏理解“覆盖”和“匹配”是两种不同的约束然后找一两道需要输出方案的树形DP题练习用标记数组记录转移路径最后挑战基环树版本看自己能不能在断环后把状态转移原封不动地套上去。这比盲目刷几十道同类型题更有效。题目包装千变万化说到底就是把“约束条件”转化成“状态设计”。状态对了代码只是顺水推舟状态错了样例越漂亮隐藏数据死得越惨。我做 P3408 最大的教训是看到“恋爱”这种带故事的题先别急着被它带着走把故事剥掉剩下“树上选边边不共享端点”这九个字再动手写状态。数学上已经证明树上最大权匹配可以线性求解而线性求解的关键就藏在这两个简简单单的 dp 数组里。希望这篇拆解能帮你少踩几个我踩过的坑。