题解：AT_abc269_h [ABC269Ex] Antichain

qczrz6v4nhp6u

2025-01-07 08:13:41

Solution

Solution

考虑 dp。设 f_{i,j} 表示在子树 i 中选 j 个点，且这 j 个点构成的集合是好的。不难得到转移：

f_{x,i}\times f_{y,j}\to f'_{x,i+j},y\in{\rm son}(x)

做完上述转移后给 f_{x,1} 加上 1 即可。复杂度 O(n^2)，需要优化。

注意到这是一个卷积的形式，考虑使用生成函数刻画。设 F_x(z)=\sum_{i\ge 0}f_{x,i}z^i，则转移相当于

F_x(z)=z+\prod_{y\in{\rm son}(x)}F_y(z)

直接做显然是优化不了的。注意到 \deg F_x(z)\le siz_x，考虑给树重剖一下。设 G_x(z)=\prod\limits_{\substack{y\in{\rm son}(x)\\y\ne{\rm heavy}(x)}}F_y(z)。

取出树上的一条重链，考虑优化这上面的转移。设 t 为这条重链的顶端，枚举这条重链上选了 0 或 1 个点，有转移：

F_t(z)=\prod_{x\in\rm chain}G_x(z)+z\sum_{x\in\rm chain}\prod_{\substack{y\in\rm chain\\{\rm dep}_y<{\rm dep}_x}}G_y(z)

由于轻儿子的 siz 总和是 O(n\log n) 级别的，上式可以通过分治 NTT 在 O(n\log^3 n) 时间内计算，而计算 G_x(z) 也可以在 O(n\log^3 n) 时间内计算。

最终时间复杂度为 O(n\log^3 n)，可以通过。

Code

#include<bits/stdc++.h>
using namespace std;
using ui=unsigned int;
using ll=long long;
using ull=unsigned long long;
using i128=__int128;
using u128=__uint128_t;
using pii=pair<int,int>;
#define fi first
#define se second
constexpr int N=524290,mod=998244353,g=3;
inline ll add(ll x,ll y){return (x+=y)>=mod&&(x-=mod),x;}
inline ll Add(ll &x,ll y){return x=add(x,y);}
inline ll sub(ll x,ll y){return (x-=y)<0&&(x+=mod),x;}
inline ll Sub(ll &x,ll y){return x=sub(x,y);}
inline ll qpow(ll a,ll b){
    ll res=1;
    for(;b;b>>=1,a=a*a%mod)
        if(b&1)res=res*a%mod;
    return res;
}
int n;vector<int> Gr[N];
using poly=vector<ll>;
int lim,rev[N];ll ilim,w[N];
void initNTT(int n){
    lim=1;
    while(lim<=n)lim<<=1;
    ilim=qpow(lim,mod-2);
    for(int i=0;i<lim;i++)
        rev[i]=(rev[i>>1]>>1)|((i&1)*(lim>>1));
    for(int i=1;i<lim;i<<=1){
        ll wn=qpow(g,(mod-1)/(i<<1)),cur=1;
        for(int j=0;j<i;j++,cur=cur*wn%mod)w[i|j]=cur;
    }
}
void NTT(ll *F,int type){
    for(int i=0;i<lim;i++)
        if(i<rev[i])
            swap(F[i],F[rev[i]]);
    for(int i=1;i<lim;i<<=1)
        for(int j=0;j<lim;j+=i<<1)
            for(int k=0;k<i;k++){
                ll x=F[j|k],y=w[i|k]*F[i|j|k]%mod;
                F[j|k]=add(x,y),F[i|j|k]=sub(x,y);
            }
    if(type==1)return;
    reverse(F+1,F+lim);
    for(int i=0;i<lim;i++)F[i]=F[i]*ilim%mod;
}
poly operator +(const poly &A,const poly &B){
    static poly C;C.resize(max(A.size(),B.size()));
    for(int i=0;i<(int)C.size();i++)C[i]=0;
    for(int i=0;i<(int)A.size();i++)Add(C[i],A[i]);
    for(int i=0;i<(int)B.size();i++)Add(C[i],B[i]);
    return C;
}
poly operator *(const poly &A,const poly &B){
    if(A.empty()||B.empty())return poly{};
    int n=A.size()-1,m=B.size()-1;
    static poly C;C.resize(n+m+1);
    for(int i=0;i<=n+m;i++)C[i]=0;
    if(1ll*n*m<=500){
        for(int i=0;i<=n;i++)
            for(int j=0;j<=m;j++)
                C[i+j]=(C[i+j]+A[i]*B[j])%mod;
    }
    else{
        static ll F[N],G[N];
        for(int i=0;i<=n;i++)F[i]=A[i];
        for(int i=0;i<=m;i++)G[i]=B[i];
        initNTT(n+m);
        for(int i=n+1;i<lim;i++)F[i]=0;
        for(int i=m+1;i<lim;i++)G[i]=0;
        NTT(F,1),NTT(G,1);
        for(int i=0;i<lim;i++)F[i]=F[i]*G[i]%mod;
        NTT(F,-1);
        for(int i=0;i<=n+m;i++)C[i]=F[i];
    }
    return C;
}
int fat[N],siz[N],son[N];
void dfs1(int x,int fa){
    siz[x]=1,fat[x]=fa;
    for(auto &y:Gr[x])
        if(y!=fa){
            dfs1(y,x);
            siz[x]+=siz[y];
            if(siz[son[x]]<siz[y])
                son[x]=y;
        }
}
poly F[N],G[N];
poly solve1(const vector<int> &vec,int l,int r){
    if(l+1==r)return F[vec[l]];
    int mid=(l+r)>>1;
    return solve1(vec,l,mid)*solve1(vec,mid,r);
}
pair<poly,poly> solve2(const vector<int> &vec,int l,int r){
    if(l+1==r)return make_pair(poly{1},G[vec[l]]);
    int mid=(l+r)>>1;
    auto res1=solve2(vec,l,mid),res2=solve2(vec,mid,r);
    return make_pair(res1.fi+res1.se*res2.fi,res1.se*res2.se);
}
void dfs2(int x,int fa){
    vector<int> vec;
    for(auto &y:Gr[x])
        if(y!=fa){
            dfs2(y,x);
            if(y!=son[x])
                vec.emplace_back(y);
        }
    if(!vec.size())G[x]=poly{1};
    else G[x]=solve1(vec,0,vec.size());
    if(son[fat[x]]!=x){
        vec.clear(),vec.shrink_to_fit();
        for(int u=x;u;u=son[u])vec.emplace_back(u);
        auto res=solve2(vec,0,vec.size());
        F[x]=res.se+poly{0,1}*res.fi;
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=2;i<=n;i++){
        int p;cin>>p;
        Gr[p].emplace_back(i);
    }
    dfs1(1,0),dfs2(1,0);
    for(int i=1;i<(int)F[1].size();i++)cout<<F[1][i]<<'\n';
    for(int i=(int)F[1].size();i<=n;i++)cout<<0<<'\n';
    return 0;
}