题解 P4201 【[NOI2008]设计路线 】

Sooke · 2019-02-06 22:44:32 · 题解

解题思路

先来看一句至关重要的题意：

Z 国的每个城市所处的经度都不相同，并且最多只和一个位于它东边的城市直接通过公路相连。

解读一下，就是点 i 要么向 [1,\ i-1] 中的某一点连边，要么不连。言下之意，Z 国是个森林。那么：

如果某个城市无法到达首都，则输出两行 -1。

就很好判断了，只有树才是连通的森林，而树必定有 n - 1 条边，故先判掉 m \neq n - 1 。

于是乎，我们的问题就放在了一棵树上，大致的题意就是：

给树路径剖分，使根出发路径经过轻边的最大值最小，求最小值和合法剖分方案数。

第一问格外符合树形 dp 的模型，怎么设计这个 dp 呢？

容易想到，用 f_{i,\,u} 表示点 u 往不超过 i 个儿子的边修成了铁路，子树内结点不便利值的最大值，显然 i \in [0,\,2] 。直接算不超过 i 不好算，注意下面是先算出等于 i 的，然后前缀 \min 转换。

树形 dp 最经典的转移方式：扫过每个儿子，一个一个计算贡献。设计算儿子 v 的贡献前，f_{i,\,u} 的值是 f'_{i,\,u} 。

从易到难，首先是 i = 0 的转移：

原理：既然不修建铁路，子树 v 里面怎么修铁路就管不着了，所以引用的是 f_{2,\,v} ，并且不便利值也会因为这条轻边整体 + 1 。

然后是 i = 1 的转移：

原理：不修建铁路的原理和上一个转移是一样的，这里多了一个修建铁路，所以 u,\,v 两边都得少一条，轻边都修成了重边，+ 1 扔掉。