【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 <bits/stdc++.h>
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;
}