CF543D Road Improvement 题解
Link.
Codeforces
Luogu
Description.
\(n\) 个点的树，给边染色。
一个合法的方案定义为所有点到 \(x\) 的路径上只有一条黑边。
对所有 \(x\) 求出合法方案方案数。
Solution.
哈哈，这题我出思路用了 1min，然后被代码细节折磨了 4+h！！！！出题人死个马
首先定义 \(f_{x,0}\) 和 \(f_{x,1}\) 为 \(x\) 节点祖先 没有/有 黑边的方案数。
然后有一个显然的转移，就是
挺显然的，就是枚举这条边是否染黑。
确认完正确性后，就直接开始考虑换根。
定义 \(g_{x,0},g_{x,1}\) 表示以 \(x\) 为根总共的答案。
根据换根的套路，写出了这样一份代码
感觉根本没问题，但是 WA on test 10。
就你考虑定义 \(f0,f1\) 分别如果把它父亲当作子树的贡献，那有
\(f0=\frac{g_{fa,0}}{f_{x,0}+f_{x,1}},f1=\frac{g_{fa,1}}{f_{x,1}}\)
就考虑把当前孩子的贡献去掉。
然后就调啊调啊调啊调啊，最后发现。
tm 这个 \(f_{x,0}+f_{x,1} \bmod P\) 是可以等于 \(0\) 的
然后 tm 就没逆元了，卡这个出题人怕不是马早没了。
然后直接拆一下式子，记录乘上的 \(0\) 的个数。
然后直接做就做完了，但是细节挺多的
Coding.
点击查看代码
//Coded by Kamiyama_Shiki on 2021.11.16 {{{
//是啊……你就是那只鬼了……所以被你碰到以后，就轮到我变成鬼了
#include
#define debug(...) fprintf(stderr,__VA_ARGS__)
using namespace std;typedef long long ll;
templateinline void read(T &x)
{
x=0;char c=getchar(),f=0;
for(;c<48||c>57;c=getchar()) if(!(c^45)) f=1;
for(;c>=48&&c<=57;c=getchar()) x=(x<<1)+(x<<3)+(c^48);
f?x=-x:x;
}
templateinline void read(T &x,L&...l) {read(x),read(l...);}//}}}
const int N=200005,P=1000000007;
int fc[N],fi[N],iv[N];//dbinit{{{
inline int ksm(int x,int q=P-2) {int r=1;for(;q;q>>=1,x=1ll*x*x%P) if(q&1) r=1ll*r*x%P;return r;}
inline void dbinit(int n=N-1)
{
fc[0]=1;for(int i=1;i<=n;i++) fc[i]=1ll*fc[i-1]*i%P;
iv[1]=1;for(int i=2;i<=n;i++) iv[i]=1ll*iv[P%i]*(P-P/i)%P;
fi[0]=1;for(int i=1;i<=n;i++) fi[i]=1ll*fi[i-1]*iv[i]%P;
}
inline int C(int n,int m) {return n<0||m<0||n