#include<bits/stdc++.h>
#define int long long
using namespace std;
bool Begin;
const int max_n=2000006,mod1=1000000009,mod2=998244853;
inline int read(){
    int x=0;bool w=0;char c=getchar();
    while(c<'0' || c>'9') w|=c=='-',c=getchar();
    while(c>='0' && c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
    return w?-x:x;
}
inline void write(int x){
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10^48);
}
struct graph{
    int ct,hd[max_n],to[max_n<<1],nx[max_n<<1];
    graph(){ct=1;}
    inline void add(int u,int v){
        nx[++ct]=hd[u],hd[u]=ct,to[ct]=v;
    }
}e;
inline int MOD1(int x){
    return (x>=mod1?x-mod1:x);
}
inline int MOD2(int x){
    return (x>=mod2?x-mod2:x);
}
struct Hashnum{
    int x1,x2;
    Hashnum(int A=0,int B=0):x1(A),x2(B){}
    bool operator == (const Hashnum &b) const{
        Hashnum a=*this;
        return (a.x1==b.x1 && a.x2==b.x2);
    }
    bool operator < (const Hashnum &b) const{
        Hashnum a=*this;
        return (a.x1<b.x1 || (a.x1==b.x1 && a.x2<b.x2));
    }
    Hashnum operator * (const Hashnum &b) const{
        Hashnum a=*this;
        return Hashnum(a.x1*b.x1%mod1,a.x2*b.x2%mod2);
    }
    Hashnum operator + (const Hashnum &b) const{
        Hashnum a=*this;
        return Hashnum(MOD1(a.x1+b.x1),MOD2(a.x2+b.x2));
    }
    Hashnum operator - (const Hashnum &b) const{
        Hashnum a=*this;
        return Hashnum(MOD1(a.x1-b.x1+mod1),MOD2(a.x2-b.x2+mod2));
    }
    Hashnum operator * (const int &b) const{
        Hashnum a=*this;
        return a*Hashnum(b,b);
    }
    Hashnum operator + (const int &b) const{
        Hashnum a=*this;
        return a+Hashnum(b,b);
    }
    Hashnum operator - (const int &b) const{
        Hashnum a=*this;
        return a-Hashnum(b,b);
    }
}hs;

int n,sz[max_n],mxs[max_n];

inline void dfs1(int u,int fa){
    sz[u]=1;
    for(register int i=e.hd[u];i;i=e.nx[i]){
        int v=e.to[i];
        if(v==fa) continue;
        dfs1(v,u);
        sz[u]+=sz[v];
        mxs[u]=max(mxs[u],sz[v]);
    }
    mxs[u]=max(mxs[u],n-sz[u]);
}
int zx,zx2;
inline void dfs2(int u,int fa){
    zx=u;
    for(register int i=e.hd[u];i;i=e.nx[i]){
        int v=e.to[i];
        if(v==fa) continue;
        if(sz[v]>n/2)
            dfs2(v,u);
    }
}

int ans[max_n],tong[max_n],pw1[max_n],pw2[max_n];

int B1=114514,B2=11037;

map<Hashnum,int> mp;
inline void dfs3(int u,int fa,Hashnum hs){
    for(register int i=e.hd[u];i;i=e.nx[i]){
        int v=e.to[i];
        if(v==fa || v==zx || v==zx2) continue;
        Hashnum t=hs-Hashnum(pw1[mxs[v]+1],pw2[mxs[v]+1])+Hashnum(pw1[mxs[v]],pw2[mxs[v]]);
        ++mp[t];
        dfs3(v,u,t);
    }
}

bool End;
#define File "forest"
signed main(){
    // #ifndef ONLINE_JUDGE
    // freopen(File ".in","r",stdin);
    // freopen(File ".out","w",stdout);
    // #endif
    // cerr<<"Memory : "<<(&Begin-&End)/1024.0/1024<<"\n";
    n=read();
    for(register int i=1;i<n;++i){
        int u=read(),v=read();
        e.add(u,v),e.add(v,u);
    }
    dfs1(1,-1);
    dfs2(1,-1);
    for(register int i=1;i<=n;++i)
        ++tong[mxs[i]+1];
    ++tong[n];
    if(!(n&1)) for(register int i=1;i<=n;++i)
        if(i!=zx && mxs[i]==mxs[zx]){
            zx2=i;
            break;
        }
    for(register int i=1;i<=n;++i){
        hs.x1=(hs.x1*B1+tong[i]),
        hs.x2=(hs.x2*B2+tong[i]);
    }
    pw1[n]=pw2[n]=1;
    for(register int i=n-1;i;--i){
        pw1[i]=pw1[i+1]*B1%mod1,
        pw2[i]=pw2[i+1]*B2%mod2;
    }
    ++mp[hs-Hashnum(pw1[mxs[zx]+1],pw2[mxs[zx]+1])+Hashnum(pw1[mxs[zx]],pw2[mxs[zx]])];
    if(zx2) ++mp[hs-Hashnum(pw1[mxs[zx2]+1],pw2[mxs[zx2]+1])+Hashnum(pw1[mxs[zx2]],pw2[mxs[zx2]])];
    dfs3(zx,-1,hs);
    if(zx2) dfs3(zx2,-1,hs);
    int cnt=0;
    for(auto i=mp.begin();i!=mp.end();++i)
        ans[++cnt]=(*i).second;
    sort(ans+1,ans+1+cnt);
    write(cnt),putchar('\n');
    for(register int i=1;i<=cnt;++i)
        write(ans[i]),putchar('\n');
    return 0;
}

0 条评论

目前还没有评论...

信息

ID
5555
时间
1000ms
内存
256MiB
难度
6
标签
递交数
5
已通过
1
上传者