【Codeforces】 CF1762E Tree Sum

题目链接

CF方向
Luogu方向

题目解法

首先考虑 $n$ 为奇数的情况无解，这个可以通过乘积矛盾简单证明

接下来考虑一个结论是：偶数个点的树的形态确定之后，只有恰好 $1$ 种染色方案，即从叶子一层一层往上面染，这样一定可以构造出来解且唯一

考虑一个更强的结论是：一条边的边权为 $1$ 当且仅当这条边对应的两个子树大小都为偶数
为什么？考虑 $siz$ 为奇数的情况一定不可能点全部合法，但又要使它合法，只能让子树根的乘积为 $1$，然后令上面连向整体的边为 $-1$ 即可
$siz$ 全为偶数的情况用反证法不难证出

现在有一个很重要的 $trick$（我也要提醒我自己！！！）是：对于每条边考虑它的贡献，然后类和
这样就好算了，对于一条连接大小为 $i,n-i$ 的子树的边（必须在 $1-n$ 路径上），贡献为 $\left(\genfrac{}{}{0ex}{}{n-2}{i-1}\right)f_i{f}_{n-i}i(n-i)$
其中 $f_i$ 为 $i$ 个点的树的形态方案数，即为 $i^{i-2}$
时间复杂度 $O(nlogn)$

#include 
using namespace std;
const int N=500100,P=998244353;
int n,fac[N],inv[N],f[N];
inline int read(){
    int FF=0,RR=1;
    char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;
    for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;
    return FF*RR;
}
int qmi(int a,int b){
    int res=1;
    for(;b;b>>=1){
        if(b&1) res=1ll*res*a%P;
        a=1ll*a*a%P;
    }
    return res;
}
int C(int a,int b){
    if(a<b||b<0) return 0;
    return 1ll*fac[a]*inv[b]%P*inv[a-b]%P;
}
int main(){
    n=read();
    if(n&1){ puts("0");exit(0);}
    fac[0]=1;
    for(int i=1;i<=n;i++) fac[i]=1ll*fac[i-1]*i%P;
    inv[n]=qmi(fac[n],P-2);
    for(int i=n-1;i>=0;i--) inv[i]=1ll*inv[i+1]*(i+1)%P;
    f[1]=1;
    for(int i=2;i<=n;i++) f[i]=qmi(i,i-2);
    int ans=0;
    for(int i=1,neg=-1;i<n;i++,neg*=-1) ans=(ans+1ll*neg*C(n-2,i-1)*f[i]%P*f[n-i]%P*i%P*(n-i))%P;
    printf("%d\n",(ans+P)%P);
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38