1 条题解
-
1
显然，对于一个不是重心的节点，删掉这个点后的连通块里面，最大的连通块就是包含重心的连通块。因此如果叶子添加在重心头上，别的点权值都要加一，重心不变。（对于两个重心的情况，在一个重心上加点时，显然另一个重心权值是要加一的。）
考虑如果不加在重心上。注意到上面提到的性质，哪些节点的权值会改变（如图 1，3 号节点是重心，把它当作根）：
假设我们向 9 号节点添加一个叶子，来分类讨论。
- 和被添加叶子的点不在同一子树（如 1,2,6,7 号点），显然权值都会加一。
- 和被添加叶子点在同一侧，不在这个点到根的路径上（如 5,10 号点），考虑到删掉后其最大连通块是根的那一侧，因此权值也会加一。
- 重心（如 3 号点），若被添加叶子点在重心的最大子树内，则重心权值加一；否则不变。
- 被添加叶子节点本身（如 9 号点），显然不变。
- 重心和被添加叶子点路径上的点（如 4 号点），因为删掉它后新叶子没有连通到根，所以不变。
总结一下，如果新叶子在重心的最大子树内，不会改变的就是重心到它的链（不包括两端）；否则，不会改变的是重心到它的链（包括重心，不包括被添加节点）。
我们要维护的是所有点贡献的集合，考虑从重心出发深搜整颗树，到达一个点时，只需要修改这一个点的贡献即可。可以用 Hash 实现。
注意到集合是无序的，如果和我考场降智 naive 地用每个点权值的 次方和（ 为常量）当 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; }
- 1
