关于 https://codeforces.com/blog/entry/112709 ，我的评价是：
你说得对，但是原神，后边忘了
算了。
[WC2019] 数树
神题。
看到题后我的第一反应是：
白云哭了。
所以我也哭了。一个个看吧。
以下设 \(E_1\) 是第一棵树的边集，\(E_2\) 是第二棵树的边集。
op=0
送温暖。答案显然是：
\[y^{n-|E_1\cap E_2|} \]那直接算就行了。
namespace solve0{
set<pair<int,int> >s;
void main(){
int ans=n;
for(int i=1;i<n;i++){
int u,v;scanf("%d%d",&u,&v);
if(u>v)swap(u,v);
s.insert(make_pair(u,v));
}
for(int i=1;i<n;i++){
int u,v;scanf("%d%d",&u,&v);
if(u>v)swap(u,v);
if(s.find(make_pair(u,v))!=s.end())ans--;
}
printf("%d\n",qpow(y,ans));
}
}
op=1
好我直接似了。现在答案是这个东西：
\[\sum_{E_2}y^{n-|E_1\cap E_2|} \]有个憨批式子叫子集反演：
\[f(S)=\sum_{T\subseteq S}\sum_{P\subseteq T}(-1)^{|T|-|P|}f(P) \]那设个 \(f(S)=y^{n-|S|}\) 推式子：
\[\begin{aligned} &\sum_{E_2}y^{n-|E_1\cap E_2|}\\ =&\sum_{E_2}f(E_1\cap E_2)\\ =&\sum_{E_2}\sum_{T\subseteq E_1\cap E_2}\sum_{P\subseteq T}(-1)^{|T|-|P|}f(P)\\ =&\sum_{E_2}\sum_{T\subseteq E_1\cap E_2}\sum_{P\subseteq T}(-1)^{|T|-|P|}y^{n-|P|}\\ =&\sum_{E_2}\sum_{T\subseteq E_1\cap E_2}y^{n-|T|}\sum_{P\subseteq T}(-y)^{|T|-|P|}\\ =&\sum_{E_2}\sum_{T\subseteq E_1\cap E_2}y^{n-|T|}\sum_{i=0}^{|T|}\binom{|T|}i(-y)^{|T|-i}\\ =&\sum_{E_2}\sum_{T\subseteq E_1\cap E_2}y^{n-|T|}(1-y)^{|T|}\\ =&\sum_{T\subseteq E_1}y^{n-|T|}(1-y)^{|T|}g(T) \end{aligned} \]其中 \(g(T)\) 为包含边集 \(T\) 的树个数。由 prufer 序列容易得到
\[g(T)=n^{k-2}\prod_{i=1}^ka_i \]其中 \(k\) 是连通块个数（也就是 \(n-|T|\)）， \(a_i\) 是第 \(i\) 个连通块大小。
那么代回原式：
\[\begin{aligned} &\sum_{T\subseteq E_1}y^{n-|T|}(1-y)^{|T|}g(T)\\ =&\sum_{T\subseteq E_1}y^k(1-y)^{n-k}n^{k-2}\prod_{i=1}^ka_i\\ =&\frac{(1-y)^n}{n^2}\sum_{T\subseteq E_1}\prod_{i=1}^k\frac{ny}{1-y}a_i \end{aligned} \]考虑一下怎么算后边一堆东西。设个 \(dp_{x,i}\) 为 \(x\) 的子树内 \(x\) 所在连通块大小为 \(i\) 的答案。这样就是 \(O(n^2)\) 的。
使用 CF917D 的 trick，将连通块大小转化为连通块内选一个关键点的贡献，那么就变成了 \(dp_{x,0/1}\)。这两道题的转移是一样的。复杂度 \(O(n)\)。
namespace solve1{
struct node{
int v,next;
}edge[200010];
int t,head[100010];
void add(int u,int v){
edge[++t].v=v;edge[t].next=head[u];head[u]=t;
}
int val,dp[100010][2];
void dfs(int x,int f){
dp[x][0]=1;dp[x][1]=val;
for(int i=head[x];i;i=edge[i].next){
if(edge[i].v!=f){
dfs(edge[i].v,x);
dp[x][1]=(1ll*dp[x][1]*(dp[edge[i].v][0]+dp[edge[i].v][1])%mod+1ll*dp[x][0]*dp[edge[i].v][1]%mod)%mod;
dp[x][0]=1ll*dp[x][0]*(dp[edge[i].v][0]+dp[edge[i].v][1])%mod;
}
}
}
void main(){
if(y==1){
printf("%d\n",qpow(n,n-2));return;
}
for(int i=1;i<n;i++){
int u,v;scanf("%d%d",&u,&v);
add(u,v);add(v,u);
}
val=1ll*n*y%mod*qpow(1-y+mod,mod-2)%mod;
dfs(1,0);
int ans=1ll*dp[1][1]*qpow(1-y+mod,n)%mod*qpow(1ll*n*n%mod,mod-2)%mod;
printf("%d\n",ans);
}
}
op=2
可能还好？首先我们套上一问结论知道答案是
\[\begin{aligned} &\sum_{T\subseteq E_1}y^{n-|T|}(1-y)^{|T|}g(T)^2\\ =&\frac{(1-y)^n}{n^4}\sum_{T\subseteq E_1}\prod_{i=1}^k\frac{n^2y}{1-y}a_i^2 \end{aligned} \]考虑每个连通分量的贡献。由于 \(a\) 个点的生成树有 \(a^{a-2}\) 个，所以每个连通分量的贡献是：
\[\frac{n^2y}{1-y}a_i^2a_i^{a_i-2}=\frac{n^2y}{1-y}a_i^{a_i} \]那考虑到连通分量是组成原来的森林的单位，那么有了连通分量的生成函数，求森林的生成函数直接 \(\exp\) 就行了。
namespace solve2{
int wl,a[400010],b[400010],lnb[400010],c[400010],r[400010],jc[100010],inv[100010];
void get(int n){
wl=1;
while(n>=wl)wl<<=1;
for(int i=0;i<=wl;i++)r[i]=(r[i>>1]>>1)|((i&1)<<(__lg(wl)-1));
}
const int g=3,invg=qpow(g,mod-2);
void ntt(int a[],int n,int tp){
for(int i=1;i<n;i++)if(i<r[i])swap(a[i],a[r[i]]);
for(int mid=1;mid<n;mid<<=1){
int wn=qpow(tp==1?g:invg,(mod-1)/(mid<<1));
for(int j=0;j<n;j+=mid<<1){
int w=1;
for(int k=0;k<mid;k++,w=1ll*w*wn%mod){
int x=a[j+k],y=1ll*w*a[j+mid+k]%mod;
a[j+k]=(x+y)%mod;a[j+mid+k]=(x-y+mod)%mod;
}
}
}
if(tp^1){
int inv=qpow(n,mod-2);
for(int i=0;i<n;i++)a[i]=1ll*a[i]*inv%mod;
}
}
void getinv(int n,int a[],int b[]){
if(n==1){
b[0]=qpow(a[0],mod-2);
return;
}
getinv((n+1)>>1,a,b);
wl=1;get(n<<1);
for(int i=0;i<n;i++)c[i]=a[i];
for(int i=n;i<wl;i++)c[i]=0;
ntt(b,wl,1);ntt(c,wl,1);
for(int i=0;i<wl;i++)b[i]=1ll*(2-1ll*b[i]*c[i]%mod+mod)%mod*b[i]%mod;
ntt(b,wl,-1);
for(int i=n;i<wl;i++)b[i]=0;
}
void dao(int f[],int n){
for(int i=1;i<n;i++)f[i-1]=1ll*f[i]*i%mod;
f[n-1]=0;
}
void jifen(int f[],int n){
for(int i=n;i>=1;i--)f[i]=1ll*f[i-1]*qpow(i,mod-2)%mod;
f[0]=0;
}
void getln(int n,int a[],int b[]){
for(int i=0;i<(n<<2);i++)b[i]=0;
getinv(n,a,b);
wl=1;get(n<<1);
for(int i=0;i<n;i++)c[i]=a[i];
for(int i=n;i<wl;i++)c[i]=0;
dao(c,wl);
ntt(c,wl,1);ntt(b,wl,1);
for(int i=0;i<wl;i++)b[i]=1ll*c[i]*b[i]%mod;
ntt(b,wl,-1);
jifen(b,wl);
}
void getexp(int n,int a[],int b[]){
if(n==1){
b[0]=1;return;
}
getexp((n+1)>>1,a,b);
getln(n,b,lnb);
wl=1;get(n<<1);
lnb[0]=(1-lnb[0]+a[0]+mod)%mod;
for(int i=1;i<n;i++)lnb[i]=(a[i]-lnb[i]+mod)%mod;
for(int i=n;i<wl;i++)b[i]=lnb[i]=0;
ntt(lnb,wl,1);ntt(b,wl,1);
for(int i=0;i<wl;i++)b[i]=1ll*b[i]*lnb[i]%mod;
ntt(b,wl,-1);
for(int i=n;i<wl;i++)b[i]=0;
}
void main(){
if(y==1){
printf("%d\n",qpow(n,2*(n-2)));
return;
}
jc[0]=inv[0]=1;
for(int i=1;i<=n;i++)jc[i]=1ll*jc[i-1]*i%mod,inv[i]=qpow(jc[i],mod-2);
for(int i=1;i<=n;i++)a[i]=1ll*n*n%mod*y%mod*qpow(1-y+mod,mod-2)%mod*qpow(i,i)%mod*inv[i]%mod;
getexp(n+1,a,b);
int ans=1ll*qpow(1-y+mod,n)*qpow(1ll*n*n%mod*n%mod*n%mod,mod-2)%mod*jc[n]%mod*b[n]%mod;
printf("%d\n",ans);
}
}
于是无了。
标签：数树,int,题解,sum,cap,subseteq,edge,WC2019,dp From： https://www.cnblogs.com/gtm1514/p/17114759.html