题解 CF1762E 【Tree Sum】

Leasier · 2022-12-23 10:16:09 · 题解

注意到样例中除了答案为 0 的样例 2 之外，n 均为偶数且答案非 0。

接下来我们可以观察出下面的结论：

• Observation 1：当且仅当 n 为偶数时符合条件的树存在。

证明：若一棵 n 个点的树满足条件，则 (-1)^n = ((\pm 1)^2)^{n - 1} = 1，则 n 必须为偶数。

• Observation 2：当 n 为偶数且树的形态固定，满足条件的填边权方案唯一。

证明：像 Prufer 序列那样依次给叶子与其相连的边填数并删除叶子，可以得到唯一的填数方案。

• Observation 3：一条边 (u, v) 权值为 1 当且仅当割断这条边后 u 或 v 所在连通块大小为偶数。

证明：连上前还是两边分别像上面那样填（但是把 u, v 分别当成根），若连通块大小为奇数则两边恰好只有 u, v 还得乘 -1 才可以满足条件，若连通块大小为偶数则两边都满足条件了（即直接填 1 就行）。

现在我们来考虑怎么算。

显然可以逐边算贡献。枚举 1 所在连通块大小 i，则 n 所在连通块大小为 n - i。

• 边权为 (-1)^i。
• 从剩下 n - 2 个点中选出 i - 1 个点扔到 1 那边、余下 n - i - 1 个点扔到 n 那边去，方案数为 C_{n - 2}^{i - 1}。
• 两边随便构造无根树，方案数为 f_i f_{n - i}，其中 f_n = n^{n - 2}。
• 两边随便各选一个点连边，方案数为 i(n - i)。

对每个 i 把这些东西乘起来再求和即可。时间复杂度为 O(n \log n)。

代码：

#include <stdio.h>

typedef long long ll;

const int mod = 998244353;
ll fac[500007], inv_fac[500007];

inline ll quick_pow(ll x, ll p, ll mod){
    ll ans = 1;
    while (p){
        if (p & 1) ans = ans * x % mod;
        x = x * x % mod;
        p >>= 1;
    }
    return ans;
}

inline void init(int n){
    fac[0] = 1;
    for (register int i = 1; i <= n; i++){
        fac[i] = fac[i - 1] * i % mod;
    }
    inv_fac[n] = quick_pow(fac[n], mod - 2, mod);
    for (register int i = n - 1; i >= 0; i--){
        inv_fac[i] = inv_fac[i + 1] * (i + 1) % mod;
    }
}

inline ll comb(int n, int m){
    if (n < 0 || m < 0 || n < m) return 0;
    return fac[n] * inv_fac[m] % mod * inv_fac[n - m] % mod;
}

inline ll f(int n){
    if (n == 1) return 1;
    return quick_pow(n, n - 2, mod);
}

int main(){
    int n;
    scanf("%d", &n);
    if (n % 2 == 1){
        printf("0");
        return 0;
    }
    ll ans = 0;
    init(n);
    for (register int i = 1; i < n; i++){
        if (i % 2 == 0){
            ans = (ans + (ll)i * (n - i) % mod * comb(n - 2, i - 1) % mod * f(i) % mod * f(n - i) % mod) % mod;
        } else {
            ans = ((ans - (ll)i * (n - i) % mod * comb(n - 2, i - 1) % mod * f(i) % mod * f(n - i) % mod) % mod + mod) % mod;
        }
    }
    printf("%lld", ans);
    return 0;
}