3.18 模拟赛 A

拿到这题的第一个想法是能不能树形 dp ？然后发现不太好转移。

然后考虑 $k=n-1$ 的情况，这种情况显然我们选择了每一条小边，然后发现其实我们最后选择的方案必然是一些小边合并得到的。一次合并，其实就是在某个点我们拿两个断开的边接起来。

然后我们意识到这个过程的顺序是无关紧要的，于是我们可以把每个点单独看贡献。假设一个点度数是 $deg$ ，要选择 $p$ 对点来进行操作，于是

$${deg\choose{2p}}\frac{(2p)!}{p!2^p}$$

就是方案数量（这个式子推一下就出来了）

然后我们发现每进行一次操作方案中路径数量 - 1 ，于是我们有下面这个式子

$$\sum_{p=0}^{\frac{deg}{2}}{deg\choose{2p}}\frac{(2p)!}{p!2^p} x^p\\= \sum_{p=0}^{\frac{deg}{2}} \frac{deg!}{p!(deg-2p)!2^p} x^p$$

把所有点的多项式乘起来就好了。

没想到 vector 分治多项式乘法 500ms…

#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "vector"
#include "cmath"
#include "queue"
using namespace std;
//#define int long long
#define MAXN 800006
#define pb push_back
#define fi first
#define se second
#define pii pair<int,int>
typedef long long ll;
#define P 998244353
int Pow( int x , int a ) {
    int cur = x , ans = 1;
    while( a ) {
        if( a & 1 ) ans = 1ll * ans * cur % P;
        cur = 1ll * cur * cur % P , a >>= 1;
    }
    return ans;
}
int n;
vector<int> G[MAXN];
int deg[MAXN] , d[MAXN] , inv2 = ( P + 1 ) / 2;
int J[MAXN], invJ[MAXN] , p2[MAXN];
vector<int> F[MAXN];
int wn[2][MAXN];
void getwn(int l) {
    for(int i=1;i<(1<<l);i<<=1) {
        int w0=Pow(3,(P-1)/(i<<1)),w1=Pow(3,P-1-(P-1)/(i<<1));
        wn[0][i]=wn[1][i]=1;
        for(int j=1;j<i;++j)
            wn[0][i+j]=wn[0][i+j-1]*(ll)w0%P,
                    wn[1][i+j]=wn[1][i+j-1]*(ll)w1%P;
    }
}
int rev[MAXN];
void getr(int l) { for(int i=1;i<(1<<l);++i) rev[i]=(rev[i>>1]>>1)|((i&1)<<l-1); }
void NTT(vector<int>& A,int len,int f) {
    for(int i=0;i<len;++i) if(rev[i]<i) swap(A[i],A[rev[i]]);
    for(int l=1;l<len;l<<=1)
        for(int i=0;i<len;i+=(l<<1))
            for(int k=0;k<l;++k) {
                int t1=A[i+k],t2=A[i+l+k]*(ll)wn[f][l+k]%P;
                A[i+k]=(t1+t2)%P;
                A[i+l+k]=(t1-t2+P)%P;
            }
    if( f == 1 ) for(int inv=Pow(len,P-2),i=0;i<len;++i) A[i]=A[i]*(ll)inv%P;
}
vector<int>& mul( vector<int>& a , vector<int>& b ) {
    int l1 = a.size() , l2 = b.size() , len = 1 , l = 0;
    for( int i = a.size() - 1 ; i >= 0 ; -- i ) if( !a[i] ) -- l1; else break;
    for( int i = b.size() - 1 ; i >= 0 ; -- i ) if( !b[i] ) -- l2; else break;
    while( len <= l1 + l2 ) len <<= 1 , ++ l;
    a.resize( len ); b.resize( len );
    getwn( l ) , getr( l );
    NTT( a , len , 0 ) , NTT( b , len , 0 );
    for( int i = 0 ; i < len ; ++ i ) a[i] = ( 1ll * a[i] * b[i] % P );
    NTT( a , len , 1 );
    return a;
}
vector<int>& solve( int l , int r ) {
    if( l == r ) return F[l];
    int m = l + r >> 1;
    return mul( solve( l , m ) , solve( m + 1 , r ) );
}
signed main() {
//    freopen("ex_data3.in","r",stdin);
//    freopen("out","w",stdout);
    J[0] = p2[0] = invJ[0] = 1;
    for( int i = 1 ; i < MAXN ; ++ i )
        J[i] = 1ll * J[i - 1] * i % P , invJ[i] = Pow( J[i] , P - 2 ) , p2[i] = 1ll * p2[i - 1] * inv2 % P;
    cin >> n;
    for( int i = 1 , u , v ; i < n ; ++ i ) {
        scanf("%d%d",&u,&v);
        ++ deg[u] , ++ deg[v] , G[u].push_back( v ) , G[v].push_back( u );
    }
    for( int i = 1 ; i <= n ; ++ i ) {
        for( int j = 0 ; j <= ( deg[i] / 2 ) ; ++ j ) {
            F[i].pb(1ll * J[deg[i]] * invJ[j] % P * invJ[deg[i] - 2 * j] % P * p2[j] % P);
//            cout << 1ll * J[deg[i]] * invJ[j] % P * invJ[deg[i] - 2 * j] % P * p2[j] % P << ' ';
        }
//        puts("");
    }
    random_shuffle( F + 1 , F + 1 + n );
    vector<int>& ans = solve( 1 , n );
    for( int i = n - 2 ; i >= 0 ; -- i ) {
        if( i >= ans.size() ) printf("0 ");
        else printf("%d ",ans[i]);
    }
}