- 木牛流马
求大神帮忙纠正
- 2022-10-4 11:38:59 @
#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
- 难度
- 2
- 标签
- 递交数
- 0
- 已通过
- 0
- 上传者