题解：CF1067E Random Forest Rank

zac2010 · 2025-12-17 21:42:10 · 题解

::::info[“矩阵的秩”的定义] 即一个最大的 k，满足可以选出 k 行 k 列，其交点组成的矩阵行列式不为 0。 ::::

矩阵的秩的形式不太好，我们发现它在森林中其实等于最大匹配（考虑排列置换环要对应到树上只能长为 2）。

考虑树上最大匹配直接自底向上贪心，剩下直接用树形 \text{DP} 可以做到 O(n) 维护。

::::info[DP 方法一]{open} 记 f_{u,0/1},g_{u,0/1} 表示当前 u 当前是否与某个子节点匹配的方案数与贡献和。 ::::

::::info[DP 方法二]{open} 将贡献拆成对每组匹配计数。记 f_u 为当前子树内，u 与某个子节点匹配的期望。最终答案即为 2\sum f_u。 ::::

这里给出方法二的实现：

#include <bits/stdc++.h>
#define FL(i, a, b) for (int i = (a); i <= (b); ++i)
#define FR(i, a, b) for (int i = (a); i >= (b); --i)
#define Sz(v) ((int)(v).size())
using namespace std;

typedef long long ll;

const int N = 5e5 + 10;
const int MOD = 998244353;
const int INV2 = (MOD + 1) / 2;

int n, f[N];
vector<int> G[N];

int Dfs(int u, int fa) {
    int ret = 1;
    for (int v: G[u]) {
        if (v != fa) {
            int t = Dfs(v, u);
            f[u] = (f[u] + (ll)ret * t % MOD * INV2) % MOD;
            ret = (ll)ret * (f[v] + 1) % MOD * INV2 % MOD;
        }
    }
    return ret;
}

int main() {
    scanf("%d", &n);
    FL(i, 1, n - 1) {
        int u, v;
        scanf("%d %d", &u, &v);
        G[u].emplace_back(v);
        G[v].emplace_back(u);
    }
    Dfs(1, 0);

    int ans = 0;
    FL(i, 1, n) {
        ans = (ans + f[i]) % MOD;
    }
    ans = (ll)ans * 2 % MOD;

    FL(i, 1, n - 1) {
        ans = ans * 2 % MOD;
    }
    printf("%d\n", ans);
    return 0;
}