P15114 题解

qbf！ · 2026-01-30 16:28:49 · 题解

算法一

首先可以发现：

• 当 k 是偶数时，约束 \forall i\in[1,n],(h_i\bmod 2)\ge\sum_{j\in\mathrm{child(i)}}(g_j\bmod 2) 成立，当且仅当将所有 h_i 为奇数的点取出，并在树中相邻且均为奇数的两个点之间连边后，所得图存在一组完美匹配。

• 当 k 为奇数时，上述约束成立，当且仅当 h_1 为奇数，且将所有 h_i 为奇数的点取出，在树中相邻且均为奇数的两个点之间连边，并删去 1 号点后，所得图存在一组完美匹配。

设 dp_{i,t,j} 表示以 i 为根的子树中，当点 i 是否与其父节点匹配的状态为 t\in\{0,1\}，且子树内 \sum h = j 时的最小总代价。朴素实现的时间复杂度为 \mathcal O(nk^2)，空间复杂度为 \mathcal O(nk)。

可以通过子任务 1\sim 2，期望得分 10 分。

算法二

下面通过费用流模型证明 dp_{i,0} 在偶数位置上的凸性。

构造一个包含 n(k+2)+2 个点的最小费用流网络，其中点包括源点 S、汇点 T，点 P_{i,j}(1\le i\le n,1\le j\le k)，以及点 A_i,B_i(1\le i\le n)。 定义 dep_i 为节点 i 至根节点路径上的节点数量，按如下方式连边：

5. 对任意树边 (x,y)，若 dep_x 为奇数，则从 B_x 向 A_y 连一条容量为 1，费用为 0 的边，否则从 B_y 向 A_x 连一条容量为 1，费用为 0 的边。

第 1 类边的含义是，若从 S 连向 P_{i,j} 的边被流经，或从 P_{i,j} 连向 T 的边被流经，则 h_i\ge j。

第 2\sim 5 类边的含义是限制了若 h_i 为偶数，则必定是 P_{i,2j-1},P_{2j} 之间相互匹配；若 h_i 为奇数，则最后多出来的 P_{i,h_i} 会和某个 P_{j,h_j} 匹配。

我们还需证明，对任意固定的 i，被匹配的点 P_{i,j} 构成一个前缀。考虑反证，由 f 的凸性可知 f(a_i,b_i,c_i,j)-f(a_i,b_i,c_i,j-1) 是关于 j 递增的，故若匹配的不是一个前缀，则必定可以通过交换匹配关系将其调整为前缀形式，且不增加总费用，与最优性矛盾。

因此，流量为 F 的最小费用流的费用，加上 \sum_{i=1}^nf(a_i,b_i,c_i,0)，恰好等于 dp_{1,0,2F}。由费用流的凸性可得 dp_{i,0} 在偶数位置上的凸性。同理可证 dp_{i,1} 在奇数位置上的凸性。

利用 dp 数组的凸性，在转移过程中可以通过闵可夫斯基和进行优化，在 \mathcal O(k) 时间内完成一次合并，从而将时间复杂度降至 \mathcal O(nk)。

朴素时间的空间复杂度为 \mathcal O(nk)，可以通过子任务 1\sim 4，期望得分 35 分。

算法三（树的形态随机生成）

此时树的深度只有 \mathcal O(\log n)，而 DP 时只需保留根到当前结点的 DP 数组，故空间复杂度是 \mathcal O(n+k\log n) 的。

输出方案可以先 DP 一次然后求出每个儿子子树内的 \sum h，然后再递归做下去，可以分析出 \mathcal O(nk) 的时间复杂度。

结合算法二，可以通过子任务 1\sim 6，期望得分 45 分。

算法四（树的形态是一条链）