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');
}
};