WC2019 数树
read(n,y,op);
iy=fpm(y,p-2);
if(op==0)algo1::main();
else if(op==1)algo2::main();
else algo3::main();op=0
令R是红树，B是蓝树。$s$是$R \cap B$构成的联通块个数。
则答案就是$y^s$。
$R\cap B$显然是森林。
所以s就是$n-|R\cap B|$。
直接用set之类的匹配就可以了。
namespace algo1{
set<pii> E;
void main(){
ll u,v;
ll ans=1;
for(ll i=1;i<=n;++i)ans=ans*y%p;
for(ll i=1;i<n;++i){
read(u,v);
if(u>v)swap(u,v);
E.insert(make_pair(u,v));
}
for(ll i=1;i<n;++i){
read(u,v);
if(u>v)swap(u,v);
if(E.count(make_pair(u,v)))ans=ans*iy%p;
}
write(ans,'\n');
}
} op=1
已知B，对于每个R求答案和。
设$z=\frac {1}{y}$。首先提出一个$y^n$，那么对于每个R贡献就是$z^{|R\cap B|}$。
枚举交集S，设$f(S)$为和B交集只有$S$的R个数，答案就是$\sum_S z^{|S|}f(S)$。
但是$f(S)$不是很好算。
设$g(S)$为S是与B交集子集的R个数，这个就很好算了。不过$g(S)$对答案的贡献是什么？
凑系数！
$z^n=(z-1+1)^n=\sum_{i=0}^n\binom{n}{i}(z-1)^i$。
所以答案就是$\sum_S(z-1)^{|S|}g(S)$。
$g(S)$怎么算？
假设$n$个点被分成了$m$个联通块，第$i$个联通块点数为$a_i$，那么生成树个数就是$n^{m-2}\prod a_i$(可以通过matrix-tree推出）
$n^{m-2}$也可以变成$\frac{n^{n-2}}{n^{|R\cap B|}}$
所以每条边的贡献就是$\frac{z-1}{n}\frac{a+b}{ab}$其中$a,b$是加这条边之前这条边两边的联通块大小。
设$f_{x,s}$为以$x$为根的子树，x所在联通块大小为$s$对答案的贡献。
可以$n^2$转移。
namespace algo2{
ll f[5005][5005],siz[5005],of[5005],inv[5005],w;
vector<ll> to[5005];
void dfs(ll x,ll fa){
f[x][1]=1;
siz[x]=1;
for(auto v:to[x])if(v!=fa){
dfs(v,x);
ll s=0;
for(ll i=1;i<=siz[v];++i)s+=f[v][i];
s%=p;
for(ll i=1;i<=siz[x];++i){
of[i]=f[x][i];
f[x][i]=f[x][i]*s%p;
}
for(ll i=1;i<=siz[x];++i)for(ll j=1;j<=siz[v];++j){
f[x][i+j]=(f[x][i+j]+of[i]*f[v][j]%p*inv[i]%p*inv[j]%p*(i+j)%p*w)%p;
}
siz[x]+=siz[v];
}
// write(x,':');
// for(ll i=1;i<=siz[x];++i)write(f[x][i],i==siz[x]?'\n':' ');
}
void main(){
ll u,v;
inv[1]=1;
for(ll i=2;i<=n;++i)inv[i]=(p-p/i)*inv[p%i]%p;
w=(p-1+iy)*inv[n]%p;
for(ll i=1;i<n;++i){
read(u,v);
to[u].push_back(v);
to[v].push_back(u);
}
dfs(1,0);
ll ans=0;
for(ll i=1;i<=n;++i){
ans=(ans+f[1][i])%p;
}
for(ll i=1;i<=n-2;++i)ans=ans*n%p;
for(ll i=1;i<=n;++i)ans=ans*y%p;
write(ans,'\n');
}
}考虑$\prod a_i$的组合意义，就是每个联通块选出一个点。
所以还可以$f_{x,0/1}$表示以x为根的子树，x所在联通块没选出/已选出一个点对答案的贡献。
时间复杂度$O(n)$
namespace algo2{
ll f[100005][2],siz[100005],of[100005],inv[100005],w;
vector<ll> to[100005];
void dfs(ll x,ll fa){
f[x][1]=1;
f[x][0]=1;
for(auto v:to[x])if(v!=fa){
dfs(v,x);
ll s=f[v][1];
of[0]=f[x][0];
f[x][0]=f[x][0]*f[v][1]%p;
of[1]=f[x][1];
f[x][1]=f[x][1]*f[v][1]%p;
f[x][0]=(f[x][0]+f[v][0]*of[0]%p*w%p)%p;
f[x][1]=(f[x][1]+(f[v][0]*of[1]+f[v][1]*of[0])%p*w%p)%p;
}
// write(x,':');
// for(ll i=1;i<=siz[x];++i)write(f[x][i],i==siz[x]?'\n':' ');
}
void main(){
ll u,v;
inv[1]=1;
for(ll i=2;i<=n;++i)inv[i]=(p-p/i)*inv[p%i]%p;
w=(p-1+iy)*inv[n]%p;
for(ll i=1;i<n;++i){
read(u,v);
to[u].push_back(v);
to[v].push_back(u);
}
dfs(1,0);
ll ans=f[1][1];
for(ll i=1;i<=n-2;++i)ans=ans*n%p;
for(ll i=1;i<=n;++i)ans=ans*y%p;
write(ans,'\n');
}
}op=2
类似的，把$y^n$提出来，设$g(S)$为包含$S$的生成树个数，则答案就是$\sum_S (z-1)^{|S|}g^2(S)$
假设S构成m个联通块，第$i$个联通块点数为$a_i$,则贡献就是$(z-1)^{n-m}n^{2m-4}\prod a_i^2$
如果枚举联通块的划分，设划分成$m$个联通块，第$i$个联通块点数为$a_i$，则$S$有$\prod a_i^{a_i-2}$种，贡献就是$(z-1)^{n-m}n^{2m-4}\prod a_i^{a_i}=(z-1)^nn^{-4}\prod((z-1)^{-1}n^2a_i^{a_i})$
把$(z-1)^nn^{-4}$提出来。
设$f_m$表示$n$个点中前$m$个点的答案。
枚举最后一个点所在的联通块大小，$f_m=\sum_{i=1}^{m} f_{m-i}(z-1)^{-1}n^2i^i\binom{m-1}{i-1}$
时间复杂度$O(n^2)$
namespace algo3{
ll f[100005],w,inv[100005],fac[100005],invf[100005],iw,ans[100005],qs[100005],qaq[100005];
void main(){
fac[0]=fac[1]=invf[0]=invf[1]=inv[1]=1;
qaq[0]=1;
qaq[1]=iy-1;
for(ll i=2;i<=n;++i){
inv[i]=(p-p/i)*inv[p%i]%p;
invf[i]=inv[i]*invf[i-1]%p;
fac[i]=fac[i-1]*i%p;
ans[i]=fpm(i,i);
qaq[i]=qaq[i-1]*qaq[1]%p;
}
--iy;
ans[1]=1;
f[0]=sqr(sqr(inv[n])%p)%p;
for(int i=1;i<=n;++i)f[0]=f[0]*y%p;
for(int i=1;i<=n;++i){
for(int j=1;j<=i;++j){
f[i]=(f[i]+f[i-j]*ans[j]%p*fac[i-1]%p*invf[i-j]%p*invf[j-1]%p*qaq[j-1]%p*n%p*n)%p;
}
}
write(f[n],'\n');
}
};神威士程之光：这个可以用分治FFT优化 又短又快
但是我不会这个科技。
设$f_i=i^in^2(z-1)^{-1}$,$F(x)$是$f$的指数型生成函数。
则$e^F$就是答案的指数型生成函数。
为什么？
考虑exp的定义：
$e^x=\sum_{i=0}^\infty \frac{x^i}{i!}$
所以$e^{F(x)}=\sum_{i=0}^{\infty}\frac{F^i(x)}{i!}$
相当于枚举$m$，然后枚举$m$个联通块的大小$a_1..a_m$，划分数就是$\frac{n!}{\prod a_i!}$，由于$m$个联通块是无序的，还需要$/m!$。
然后做完了。
namespace algo3{
ll f[100005],w,inv[100005],fac[100005],invf[100005],iw,ans[100005],qs[100005],qaq[100005],g[100005];
void main(){
fac[0]=fac[1]=invf[0]=invf[1]=inv[1]=1;
qaq[0]=1;
qaq[1]=iy-1;
f[1]=1;
for(ll i=2;i<=n;++i){
inv[i]=(p-p/i)*inv[p%i]%p;
invf[i]=inv[i]*invf[i-1]%p;
fac[i]=fac[i-1]*i%p;
f[i]=fpm(i,i);
qaq[i]=qaq[i-1]*qaq[1]%p;
}
--iy;
ans[1]=1;
for(ll i=1;i<=n;++i)f[i]=f[i]*qaq[i-1]%p*invf[i]%p*n%p*n%p;
w=sqr(sqr(inv[n])%p)%p;
for(ll i=1;i<=n;++i)w=w*y%p;
Polynomial::exp(n+1,f,g);
write(g[n]*fac[n]%p*w%p,'\n');
}
};