CF1554E You 题解 性质题

· · 题解

题目传送门

\text{Description}

\text{Solution}

考虑到相当于给边定向，对于每条边指向的点 i，让它 a_i+1\to a_i。

则易知总共有 2^{n-1} 个 \{a_n\}。

考虑到 k=1 的情况不太好算。

我们考虑 k>1 的情况。

这里有一个特别重要的性质。

我们令 f_x 为 x\mid k 时的答案和，当 x>1 时有 f_x\le 1。

我们简单证一下。

首先 k>1 时叶子肯定是要最后删的，这样它的 a_i=0，否则 a_i=1 与 k>1 矛盾。

然后与叶子节点相连的点就必须先删掉，也就是与叶子节点相连的边就定向了。

然后我们依次向上考虑 k 的限制，发现所有边都一定会被定向。

因此 f_x\le 1。

同时在这个证明过程中，由于 f_x\le 1，我们也能求出那个 ans_k=1 的 k。

inline int dfs(int x,int fa){
    if(!flag) return 0;
    int tot=es[x].size();
    for(re i=0;i<es[x].size();++i)
        if(es[x][i]!=fa) tot-=dfs(es[x][i],x);
    if(tot%k&&(tot-1)%k) flag=0;
    if(tot%k==0){ans=gcd(ans,tot);return 1;}
    else{ans=gcd(ans,tot-1);return 0;}
}

由于 \sum_{i=1}^na_i=n-1，因此 k\mid n-1

所以我们把每个 n-1 的因子代到上面的 k 就行啦。

时间复杂度 O(n\times d(n-1))，其中 d(n-1) 表示 n-1 的因子个数，已经比官方题解优秀那么一点点了（官方题解 O(n\times d(n-1)+n\log n)）。（

然而这个显然还可以优化。（

由于 f_x\le 1，而我们做一次 dfs 时直接可以求出那个满足 x\mid k 且 ans_k=1 的那个 k（如果 f_x\neq 0）。

那么我们可以直接找 n-1 的素因子进行 dfs，避免了大量重复的计算。

时间复杂度 O(n\times \omega(n-1))，其中 \omega(n-1) 表示 n-1 的素因子个数。

\text{Code}

const int N=1e5+5,mod=998244353;
int T,n,a[N],ans,k;
bool flag;
vector<int> es[N];

inline int pw(int x,int y){
    int sum=1;
    while(y){
        if(y&1) sum=1ll*sum*x%mod;
        x=1ll*x*x%mod;y>>=1;
    }
    return sum;
}

inline int gcd(int x,int y){return y==0?x:gcd(y,x%y);}

inline int dfs(int x,int fa){
    if(!flag) return 0;
    int tot=es[x].size();
    for(re i=0;i<es[x].size();++i)
        if(es[x][i]!=fa) tot-=dfs(es[x][i],x);
    if(tot%k&&(tot-1)%k) flag=0;
    if(tot%k==0){ans=gcd(ans,tot);return 1;}
    else{ans=gcd(ans,tot-1);return 0;}
}

// ----------  ---------- //

int main(){
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
    rd(T);
    while(T--){
        rd(n);
        for(int i=1,x,y;i<n;++i){
            rd(x);rd(y);es[x].pb(y);es[y].pb(x);
        }
        int maxn=n-1;
        for(re i=2;i*i<=maxn;++i)
            if(maxn%i==0){
                flag=1;ans=0;k=i;dfs(1,0);
                if(flag) a[ans]=1;
                while(maxn%i==0) maxn/=i;
            }
        if(maxn>1){
            flag=1;ans=0;k=maxn;dfs(1,0);
            if(flag) a[ans]=1;
        }
        a[1]=pw(2,n-1);
        for(re i=2;i<=n;++i) a[1]=(a[1]-a[i]+mod)%mod;
        for(re i=1;i<=n;++i) wr(a[i]),putchar(' ');puts("");
        for(re i=1;i<=n;++i) a[i]=0,es[i].clear();
    }
    return 0;
}

// ---------- Main ---------- //