一、题意理解

我们有一棵 $m$ 个节点的树，其中：

• 节点 $1 \dots n$ 是正确节点，节点 $n+1 \dots m$ 是错误节点。
• 从 $1$ 到 $n$ 的路径上节点编号递增（这条路径是主链）。
• 存档只能在正确节点上设置，且 $1$ 和 $n$ 必须存档，总共存档次数 $\le p$。
• 玩家从 $1$ 出发，每次在当前节点等概率选择一个儿子走。
• 如果走到错误叶子，下一步会读档（回到当前存档点）。
• 如果走到一个存档位置 $j$（且 $j$ 大于当前存档点 $i$），则存档点更新为 $j$。
• 走到正确叶子 $n$ 时结束。
• 目标是选择存档位置（除了 $1$ 和 $n$ 外再选 $p-2$ 个正确节点），使得从 $1$ 到 $n$ 的期望步数最小。

---

二、样例分析

样例：

n=3, m=7, p=2
边：
1 4
2 5
3 6
3 7

存档次数 $p=2$，必须存 $1$ 和 $3$，没有额外选择。

实际上输入是： 1→4
2→5
3→6
3→7

所以树是：

    1
   / \
  4   2
     / \
    5   3
       / \
      6   7

$1\to 2\to 3$ 是主链。

---

计算期望

存档点：$1$ 和 $3$。

从 $1$ 出发：

• 有 $2$ 个儿子：$4$（错误节点）和 $2$（正确节点）。
• 概率 $1/2$ 到 $4$（错误叶子），走 $1$ 步到 $4$，然后读档回到 $1$，总步数 = $1 + E_1$（其中 $E_1$ 是从 $1$ 开始的期望）。
• 概率 $1/2$ 到 $2$，走 $1$ 步到 $2$，然后从 $2$ 继续。

从 $2$ 出发：

• 有 $2$ 个儿子：$5$（错误叶子）和 $3$（存档点）。
• 概率 $1/2$ 到 $5$：走 $1$ 步到 $5$，读档回到 $1$，总步数 = $1 + E_1$。
• 概率 $1/2$ 到 $3$：走 $1$ 步到 $3$（存档），然后结束（因为 $3=n$）。

设 $E_1$ 为从 $1$ 开始的期望步数，$E_2$ 为从 $2$ 开始的期望步数。

方程： $E_2 = \frac12 (1 + E_1) + \frac12 \cdot 1$ 因为到 $5$ 要读档回到 $1$，到 $3$ 就结束（步数 $1$）。

$E_1 = \frac12 (1 + E_1) + \frac12 (1 + E_2)$ 因为到 $4$ 读档回到 $1$，到 $2$ 则继续。

解得： $E_2 = 0.5(2 + E_1) + 0.5 \cdot 1$
$= 1 + 0.5E_1 + 0.5$
$= 1.5 + 0.5E_1$。

$E_1 = 0.5(2 + E_1) + 0.5(1 + E_2)$
$= 1 + 0.5E_1 + 0.5 + 0.5E_2$
$= 1.5 + 0.5E_1 + 0.5E_2$。

代入 $E_2$： $E_1 = 1.5 + 0.5E_1 + 0.5(1.5 + 0.5E_1)$
$= 1.5 + 0.5E_1 + 0.75 + 0.25E_1$
$= 2.25 + 0.75E_1$
$0.25E_1 = 2.25$
$E_1 = 9$。

符合样例。

---

三、问题抽象

我们有一条主链 $1,2,\dots,n$，每个节点 $i$ 可能有一些错误子树。

存档点选择在主链的正确节点上，目标是最小化从 $1$ 到 $n$ 的期望步数。

---

四、动态规划思路

设 $f[i][k]$ 表示当前存档点在 $i$，还剩 $k$ 次存档机会（包括当前节点 $i$ 的存档）时，走到 $n$ 的期望步数。

转移：

• 如果在 $i$ 不设下一个存档点（即 $k$ 次机会留给后面），则从 $i$ 出发，可能走到错误子树（读档回到 $i$）或走到儿子 $i+1$（继续）。
• 如果在 $i$ 设下一个存档点 $j$，则走到 $j$ 后存档点更新为 $j$。

实际上更常见的状态设计： $dp[i][j]$ 表示当前存档点在 $i$，下一个存档点在 $j$（$i < j$）时，从 $i$ 走到 $j$ 的期望步数。

那么总期望就是 $\sum_{k=0}^{p-2} dp_{c_k, c_{k+1}}$，其中 $c_0=1, c_{p-1}=n$。

---

五、计算 $dp[i][j]$

从 $i$ 出发，目标走到 $j$（存档点），中途不经过其它存档点。

对于主链上的节点 $x \in [i,j)$：

• 从 $x$ 出发，有若干儿子，其中一个是 $x+1$（主链下一个），其它可能是错误子树。
• 设 $deg(x)$ 是 $x$ 的儿子数。
• 走到 $x+1$ 的概率是 $1/deg(x)$，走到任意一个错误子树的概率是 $(deg(x)-1)/deg(x)$。

如果走到错误子树：

• 期望步数 = 走到错误叶子的期望步数 + 1（读档步） + 从 $i$ 重新开始的期望步数。

这会导致方程： 设 $E_x$ 表示从 $x$ 开始，存档点在 $i$，目标走到 $j$ 的期望步数。

对于 $x = j$：$E_j = 0$（已经到达目标存档点）。

对于 $x < j$： $ E_x = 1 + \frac{1}{deg(x)} E_{x+1} + \frac{deg(x)-1}{deg(x)} (T_x + 1 + E_i) $ 其中 $T_x$ 是从 $x$ 出发走到错误叶子的期望步数（不读档）。

---

六、计算 $T_x$

对于错误子树，从 $x$ 走到错误叶子的期望步数：

• 如果 $x$ 是叶子：$T_x = 0$（但 $x$ 是正确节点，不会直接是错误叶子，这里指错误子树里的节点） 实际上 $T_u$ 对于错误节点 $u$： $ T_u = 1 + \frac{1}{deg(u)} \sum_{v \in son(u)} T_v $ 如果 $u$ 是错误叶子，则 $deg(u)=0$，$T_u=0$。

我们可以预处理所有错误节点的 $T_u$。

---

七、优化与实现

我们可以预处理 $g[i][j] = dp[i][j]$，然后利用动态规划选择存档点： 设 $F[i][k]$ 表示当前存档点在 $i$，还剩 $k$ 次存档机会，到 $n$ 的最小期望步数。 $ F[i][k] = \min_{i < j \le n} \big( dp[i][j] + F[j][k-1] \big) $ 初始 $F[n][1] = 0$，答案 $F[1][p]$。

复杂度：预处理 $dp$ 是 $O(n^3)$，选择存档点是 $O(n^2 p)$，在 $n \le 700$ 时可过。

---

八、代码框架（C++）

//#define Plus_Cat ""
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
#define ll long long
#define RCL(a,b,c,d) memset(a,b,sizeof(c)*(d))
#define FOR(i,a,b) for(int i(a);i<=(int)(b);++i)
#define DOR(i,a,b) for(int i(a);i>=(int)(b);--i)
#define tomax(a,...) ((a)=max({(a),__VA_ARGS__}))
#define tomin(a,...) ((a)=min({(a),__VA_ARGS__}))
#define EDGE(g,i,x,y) for(int i=(g).h[(x)],y=(g)[(i)].v;~i;y=(g)[(i=(g)[i].nxt)>0?i:0].v)
#define main Main();signed main(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);return Main();}signed Main
using namespace std;
constexpr int N(700 + 10), M(1500 + 10);
constexpr double DINF(1e100);

struct Ecat {
#define DE(...) E(#__VA_ARGS__,__VA_ARGS__)
    template<class T>void operator()(const char *fmt, const T a) {
        cerr << fmt << ":" << a << ".\n";
    }

    template<class T, class...Types>void operator()(const char *fmt, const T a, const Types ...args) {
        while (*fmt^',')
            cerr << *fmt++;

        return cerr << ':' << a << ", ", (*this)(++fmt, args...);
    }
} E;

int Cas, n, m, Q;
int deg[M];
double w[M], c[N][N], f[N][N];
vector<int> g[M];

void dfs(int u) {
    w[u] = 1;

    for (int v : g[u])
        dfs(v), w[u] += w[v] / deg[u];
}
#define mid ((l+r)>>1)
void Sep(const int p, int l, int r, int L, int R) {
    if (l > r)
        return;

    int Mid(L);
    f[p][mid] = DINF;
    FOR(i, L, min(R, mid - 1)) {
        double tmp(f[p - 1][i] + c[i][mid]);

        if (tmp < f[p][mid])
            f[p][mid] = tmp, Mid = i;
    }
    Sep(p, l, mid - 1, L, Mid), Sep(p, mid + 1, r, Mid, R);
}
#undef mid
int Cmain() {
    /*DE("Input");*/
    cin >> n >> m >> Q;
    FOR(i, n + 1, m) {
        int u, v;
        cin >> u >> v, g[u].push_back(v);
    }
    /*DE("DP on Tree");*/
    FOR(u, 1, m)deg[u] = (int)g[u].size() + (u < n);
    FOR(u, 1, n - 1) {
        dfs(u), w[u] = 0;

        for (int v : g[u])
            w[u] += w[v];
    }
    /*DE("DP on Line");*/
    FOR(i, 1, n) {
        c[i][i] = 0;
        FOR(j, i + 1, n)c[i][j] = c[i][j - 1] * deg[j - 1] + deg[j - 1] + w[j - 1];
    }
    FOR(i, 2, n)f[1][i] = DINF;
    f[1][1] = 0;
    FOR(i, 2, Q)Sep(i, 1, n, 1, n);
    /*DE("Output");*/
    cout << fixed << setprecision(4) << f[Q][n] << endl;
    /*DE("Clear");*/
    FOR(i, 1, m)g[i].clear();
    return 0;
}

signed main() {
#ifdef Plus_Cat
    freopen(Plus_Cat ".in", "r", stdin), freopen(Plus_Cat ".out", "w", stdout);
#endif

    for (cin >> Cas; Cas; --Cas)
        Cmain();

    return 0;
}

---

九、总结

本题的关键在于：

1. 理解存档机制和读档规则对期望步数的影响。
2. 将问题分解为计算相邻存档点之间的期望步数。
3. 利用动态规划选择最优的存档位置。
4. 注意走到错误叶子时额外的一步读档时间。