Luogu6653 造林 | Arahc's Home

题面

简化题意

给定一个树，定义一个节点的权值为删去这个节点后的图中最大连通块的大小。定义树的品种为所有节点权值构成的可重集，两树品种相同当且仅当可重集相同。

现在要给这个树加一个叶子，求能得到多少品种的树，以及每个品种有多少种添加方法得到。

$n\leq2\times10^6$ 。

题解

显然，对于一个不是重心的节点，删掉这个点后的连通块里面，最大的连通块就是包含重心的连通块。因此如果叶子添加在重心头上，别的点权值都要加一，重心不变。（对于两个重心的情况，在一个重心上加点时，显然另一个重心权值是要加一的。）

考虑如果不加在重心上。注意到上面提到的性质，哪些节点的权值会改变（如图 1，3 号节点是重心，把它当作根）：

假设我们向 9 号节点添加一个叶子，来分类讨论。

和被添加叶子的点不在同一子树（如 1,2,6,7 号点），显然权值都会加一。
和被添加叶子点在同一侧，不在这个点到根的路径上（如 5,10 号点），考虑到删掉后其最大连通块是根的那一侧，因此权值也会加一。
重心（如 3 号点），若被添加叶子点在重心的最大子树内，则重心权值加一；否则不变。
被添加叶子节点本身（如 9 号点），显然不变。
重心和被添加叶子点路径上的点（如 4 号点），因为删掉它后新叶子没有连通到根，所以不变。

总结一下，如果新叶子在重心的最大子树内，不会改变的就是重心到它的链（不包括两端）；否则，不会改变的是重心到它的链（包括重心，不包括被添加节点）。

我们要维护的是所有点贡献的集合，考虑从重心出发深搜整颗树，到达一个点时，只需要修改这一个点的贡献即可。可以用 Hash 实现。

注意到集合是无序的，如果和我考场降智 naive 地用每个点权值的 $k$ 次方和（ $k$ 为常量）当 Hash 函数，注意到 $a^k + b^k = c^k$ 在 $k\leq\log\max(a,b,c)$ 时分布不少，很大概率被卡掉。因此考虑维护每个点权值构成的桶，对这个桶进行字符串 Hash 即可。

单 Hash 也被卡了（我运气背还是出题人毒瘤还是生日悖论再现都有可能），建议双 Hash，我用的双模 Hash + 双底数。

剩下的都是一些细节问题，例如两个重心的情况，可以考虑断掉中间的边，拆成两棵树考虑（在一棵树上时反正另一棵树点的贡献都是要加一的），等等。

代码

#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;
}