WC2019 T1 数树

传送门（）

Question 0

对于给定的两棵树，设记两颗树 \(A,B\) 的重边数量为 \(R(A,B)\)，那么

\[ Ans=y^{n-R(A,B)} \]

Question 1

给定其中一棵树，求第二棵树的所有情况下答案的总和

不妨令 \(y=y^{-1}\) ,最终答案就是 \(y^{-n}y^{R(A,B)}\)。

在给定 \(A\) 的情况下，只需要统计 \(\sum\limits_B y^{R(A,B)}\) 即可

注意到\(y^k=[(y-1)+1]^k=\sum\limits_{i=0}^k (y-1)^i \binom{k}{i}\)

及对于确定的 \(A,B\)，枚举一个边集 \(S\) ，若 \(S\) 中每一条边均为 \(A,B\) 重边，则其贡献为 \((y-1)^{|S|}\) 否则为 \(0\)

特别的，我们把 \(y-1=0​\) 特判掉，因为不存在逆元。

考虑枚举每一个 \(A​\) 的边集，假设一共 \(n-m​\) 条边把 \(n​\) 个点划分成了 \(m​\) 个联通块。

设第 \(i​\) 个联通块有 \(a_i​\) 个点那么它的贡献为 \((y-1)^{n-m}\times​\) 包含这\(n-m​\) 条边的树的个数。

把每一个联通块当作一个点，考虑枚举每个联通块的度数 \(d_i\) 通过 \(prufer\) 序列我们知道答案为

\[ Ans=(y-1)^{n-m}\sum\limits_{(\sum a_i)=n,(\sum d_i)=2(m-2)} m^{m-2}(\prod_{i=1}^m a_i^{d_i})(\prod_{i=1}^m \binom{\sum_{j=1}^i(d_j-1)}{d_i-1}) \\ =(y-1)^{n-m}\sum\limits_{(\sum a_i)=n,(\sum d_i)=2m-2} m^{m-2}(\prod_{i=1}^m a_i^{d_i})\frac{(m-2)!}{\prod_{i=1}^m(d_i-1)!}\\ =(y-1)^{n-m}\sum\limits_{(\sum a_i)=n,(\sum d_i)=m-2} (\prod_{i=1}^m a_i)(m-2)!m^{m-2}\prod_{i=1}^m \frac{a_i^{d_i}}{d_i!}\\ =(y-1)^{n-m}\sum\limits_{(\sum a_i)=n} (\prod_{i=1}^m a_i)n^{m-2}\\ =(y-1)^n n^{-2}\sum\limits_{(\sum a_i)=n} (\prod_{i=1}^m a_i)n^m (y-1)^{-m}\\ =(y-1)^n n^{-2}\sum\limits_{(\sum a_i)=n} (\prod_{i=1}^m a_i(y-1)^{-1}n)\\ \]

注意 \((\prod_{i=1}^m a_i)\) 表示每个联通块中选一个关键点的方案数量，这样就可以设 \(F_{x,0/1}\) 表示 \(x\) 号点所在联通块是否选出关键点的贡献和，树形 \(DP\) ，每次考虑父子的边是否被选中即可。

Question 2

和 \(Question\ 1​\) 的做法类似，先特判 $y-1=​$0 考虑枚举一个边集构成了 $ m ​$ 个的联通块的答案

\[ Ans=(y-1)^{n-m}\sum\limits_{(\sum a_i)=n}\frac{n!}{\prod_{i=1}^m a_i!}\prod a_i^{a_i-2}\frac {1}{m!}(n^{m-2}\prod_{i=1}^m a_i)^2\\ =(y-1)^n n^{-4} n!\sum\limits_{(\sum a_i)=n}\frac {1}{m!}{\prod_{i=1}^m \frac{n^2 a_i^{a_i}}{a_i!(y-1)}}\\ \]

之需要考虑 \(F_n=\sum\limits_{(\sum a_i)=n}\frac {1}{m!}{\prod_{i=1}^m \frac{n^2 a_i^{a_i}}{a_i!(y-1)}}​\) 的结果即可。

若设大小为 $k $ 的部分的贡献为 \(G(k)=\frac{n^2 k^k}{k! (y-1)}\)，考虑 \(e^x\) 即 \(exp(x)\) 的泰勒展开式为 \(\sum_{i=0}^{+INF} \frac{x^i}{i!}\) 。

有 \(F=exp(G)\) ，那么多项式求 \(exp\) 即可。

#include
    
     #define LL long longusing namespace std;int read(){    int nm=0,fh=1; char cw=getchar();    for(;!isdigit(cw);cw=getchar()) if(cw=='-') fh=-fh;    for(;isdigit(cw);cw=getchar()) nm=nm*10+(cw-'0');    return nm*fh;}#define pii pair
     
      #define mp make_pair#define mod 998244353#define M 600010namespace  CALC{    inline int add(int x,int y){x+=y;return (x>=mod)?(x-mod):x;}    inline int mns(int x,int y){x-=y;return (x<0)?(x+mod):x;}    inline int mul(LL x,LL y){return (LL)x*(LL)y%mod;}    inline void upd(int &x,int y){x+=y;(x>=mod)?(x-=mod):0;}    inline int qpow(int x,int sq){        int res=1;        for(;sq;sq>>=1,x=mul(x,x)) if(sq&1) res=mul(res,x);        return res;    }}using namespace CALC;namespace POLY{    int lg[M],g[40],v[40],od[M],iv[40],vv[M];    void init(int N){        N<<=2; int len=2,nw=1;        for(;len<=N;len<<=1,nw++)            lg[len]=nw,v[nw]=qpow(g[nw]=qpow(3,(mod-1)/len),mod-2),iv[nw]=qpow(len,mod-2);        for(int i=1;i<=len;i++) vv[i]=qpow(i,mod-2);vv[0]=0;    }    void NTT(int *x,int len,int kd){        int bas=lg[len];        for(int i=1;i
      
       >1]>>1)|((i&1)<<(bas-1));        for(int i=1;i
       
        0)?g[tp]:v[tp],st=0;st
        
         <<1)){                for(int now=1,pos=st;pos
         
          0) return; for(int i=0;i
          
           >1); cpy(A,F,len),cpy(B,G,len),len<<=1,NTT(A,len,1),NTT(B,len,1); for(int i=0;i
           
            >=1; for(int i=len;i
            
             >=1; for(int i=len;i<(len<<1);i++) G[i]=0; } void get_exp(int *F,int *G,int len){ static int A[M],B[M]; if(len==1){G[0]=1;return;} get_exp(F,G,len>>1); cpy(A,G,len),get_ln(G,B,len); for(int i=0;i
             
              >=1; for(int i=len;i
              
                P;namespace Q1{ int fs[M],nt[M],to[M],tmp,F[M][2],K,vK,G[2]; inline void link(int x,int y){nt[tmp]=fs[x],fs[x]=tmp,to[tmp++]=y;} inline void DP(int x,int last){ F[x][0]=F[x][1]=K; for(int i=fs[x],v;i!=-1;i=nt[i]) if((v=to[i])^last){ DP(to[i],x),G[0]=0,G[1]=0; for(int j=0;j<2;j++) for(int k=0;k<2;k++){ if(!(j&k)) upd(G[j|k],mul(mul(F[x][j],F[v][k]),vK)); if(k) upd(G[j],mul(F[x][j],F[v][k])); } F[x][0]=G[0],F[x][1]=G[1]; } } inline int solve(){ memset(fs,-1,sizeof(fs)); for(int i=1,x,y;i