自动搬运

查看原文

来自洛谷，原作者为

	Sooke 做被自己雪藏的耳廓狐 | https://codeforces.com/profile/Sulfox

搬运于2025-08-24 21:57:37，当前版本为作者最后更新于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$ 的转移：

$$f_{0,\,u} = \max\{f'_{0,\,u},\ f_{2,\,v} + 1\}$$

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

然后是 $i = 1$ 的转移：

$$f_{1,\,u} = \min\{\max\{f'_{1,\,u},\ f_{2,\,v} + 1\},\ \max\{f'_{0,\,u},\ f_{1,\,v}\}\} $$

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

$i = 2$ 的转移和 $i = 1$ 是类似的，不妨自己去写写。

$$f_{2,\,u} = \min\{\max\{f'_{2,\,u},\ f_{2,\,v} + 1\},\ \max\{f'_{1,\,u},\ f_{1,\,v}\}\} $$

整理一下:

$$\text{边界} \begin{cases}f_{0,\,u} =0\\f_{1,\,u}=f_{2,\,u}=\infty\end{cases} $$$$\text{转移} \begin{cases}f_{0,\,u} = \max\{f'_{0,\,u},\ f_{2,\,v} + 1\} \\f_{1,\,u} = \min\{\max\{f'_{1,\,u},\ f_{2,\,v} + 1\},\ \max\{f'_{0,\,u},\ f_{1,\,v}\}\} \\f_{2,\,u} = \min\{\max\{f'_{2,\,u},\ f_{2,\,v} + 1\},\ \max\{f'_{1,\,u},\ f_{1,\,v}\}\}\end{cases} $$

直接 dfs 一遍求出 $f$ ，不要忘了前缀 $\min$，第一问就做完了。

---

接着做第二问，你会发现与第一问有异曲同工之妙，它仍然是这个树形 dp，但没那么简单了。

大力设一波状态，令 $g_{i,\,j,\,u}$ 表示点 $u$ 往不超过 $i$ 个儿子的边修成了铁路，子树内结点不便利值都不超过 $j$ 的方案数。

也许你会问：$i,\,j$ 都是 $n$ 级的，这一乘就 $O(n^2)$ 了，真的不会 MLE？

神奇的是，这个 $j$ 啊，以及我们第一问的答案，不超过 $\log_3n$（极限数据下 $< 11$）。感性理解下，为什么树链剖分根出发路径经过轻边数不超过 $\log_2 n$ （提示：用子树大小证明）？但树链剖分的链是直的，而非 V 字形，这题是 V 字形的路径剖分，然后仔细想想差异就明白最初的结论了。

数组开得下了，如何转移呢？

直接算不超过 $i$ 还是不好算，先算出等于 $i$ 的，然后前缀和转换。（异曲同工 1）

依旧从易到难，看 $i = 0$ 的转移式，和 $f$ 的是不是有点类似？（异曲同工 2）

$$g_{0,\,j,\,u} = g'_{0,\,j,\,u} \times g_{2,\,j-1,\,v} $$

原理很简单，不赘述了。$i \geqslant 1$ 的转移式就更像了：

$$g_{1,\,j,\,u} = g'_{1,\,j,\,u} \times \ g_{2,\,j-1,\,v} + g'_{0,\,j,\,u} \times g_{1,\,j,\,v} $$$$g_{2,\,j,\,u} = g'_{2,\,j,\,u} \times \ g_{2,\,j-1,\,v} + g'_{1,\,j,\,u} \times g_{1,\,j,\,v} $$

发现没有？原本的 $+ 1$ 变成 $- 1$ 藏在下标里了，$\min$ 变成了 $+$ ，$\max$ 变成了 $\times$ ！建议想想为什么。

附上边界整理整理，其实边界不过是把 $f$ 的 $0$ 换成了 $1$ ，$\infty$ 换成了 $0$ ：（异曲同工 3）

$$\text{边界} \begin{cases}g_{0,\,j,\,u} =1\\g_{1,\,j,\,u}=g_{2,j,\,u}=0\end{cases} $$$$\text{转移} \begin{cases}g_{0,\,j,\,u} = g'_{0,\,j,\,u} \times g_{2,\,j-1,\,v}\\g_{1,\,j,\,u} = g'_{1,\,j,\,u} \times \ g_{2,\,j-1,\,v} + g'_{0,\,j,\,u} \times g_{1,\,j,\,v}\\g_{2,\,j,\,u} = g'_{2,\,j,\,u} \times \ g_{2,\,j-1,\,v} + g'_{1,\,j,\,u} \times g_{1,\,j,\,v}\end{cases} $$

同样 dfs 求 $g$ 。求完之后答案就十分明朗了。

---

代码实现

具体实现中注意两点（针对我的代码）：

1. $g$ 的转移式中可能出现负下标，负下标的 $g$ 值当然是 $0$ 。据此，我的代码中 $f$ 的值和 $g$ 的 $j$ 下标都比现实多 $1$ ，以免负下标的出现同时使得代码整洁美观。

2. 转移式的顺序是先 $2$ 再 $1$ 最后 $0$ ，因为 $f_{2,\,u}$ 引用了 $f_{1,\,u}$ ，$f_{1,\,u}$ 引用了 $f_{0,\,u}$ ，$g$ 同理。

#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>

inline int read() {
    char c = getchar(); int x = 0;
    while (c < '0' || c > '9') { c = getchar(); }
    while (c >= '0' && c <= '9') { x = (x << 1) + (x << 3) + (c & 15); c = getchar(); }
    return x;
}

const int maxN = 100005, maxR = 12;

int n, m, p, f[3][maxN], g[3][maxR][maxN];

struct List {
    int len, fst[maxN], nxt[maxN << 1], to[maxN << 1];

    List() { memset(fst, -1, sizeof(fst)); }
    inline void insert(int u, int v) { nxt[len] = fst[u]; to[len] = v; fst[u] = len++; }
    inline void link(int u, int v) { insert(u, v); insert(v, u); }
} e;

inline int add(int x, int y) { x += y; return x >= p ? x - p : x; }
inline int mul(int x, int y) { return (long long) x * y % p; }

void dfs1(int u, int fa) {
    f[0][u] = 1; f[1][u] = f[2][u] = 1e9;
    for (int i = e.fst[u], v; ~i; i = e.nxt[i]) {
        v = e.to[i];
        if (v == fa) { continue; } dfs1(v, u);
        f[2][u] = std::min(std::max(f[2][u], f[2][v] + 1), std::max(f[1][u], f[1][v]));
        f[1][u] = std::min(std::max(f[1][u], f[2][v] + 1), std::max(f[0][u], f[1][v]));
        f[0][u] = std::max(f[0][u], f[2][v] + 1);
    }
    f[1][u] = std::min(f[0][u], f[1][u]); f[2][u] = std::min(f[1][u], f[2][u]);
}
void dfs2(int u, int fa) {
    for (int i = 1; i <= f[2][1]; i++) { g[0][i][u] = 1; }
    for (int i = e.fst[u], v; ~i; i = e.nxt[i]) {
        v = e.to[i];
        if (v == fa) { continue; } dfs2(v, u);
        for (int i = 1; i <= f[2][1]; i++) {
            g[2][i][u] = add(mul(g[2][i][u], g[2][i - 1][v]), mul(g[1][i][u], g[1][i][v]));
            g[1][i][u] = add(mul(g[1][i][u], g[2][i - 1][v]), mul(g[0][i][u], g[1][i][v]));
            g[0][i][u] = mul(g[0][i][u], g[2][i - 1][v]);
        }
    }
    for (int i = 1; i <= f[2][1]; i++) { g[1][i][u] = add(g[0][i][u], g[1][i][u]); g[2][i][u] = add(g[1][i][u], g[2][i][u]); }
}

int main() {
    n = read(); m = read(); p = read();
    if (m != n - 1) { printf("-1\n-1\n"); return 0; }
    for (int i = 1; i <= m; i++) { e.link(read(), read()); }
    dfs1(1, 0); dfs2(1, 0);
    printf("%d\n%d\n", f[2][1] - 1, g[2][f[2][1]][1]);
    return 0;
}