给一手链接 https://www.luogu.com.cn/problem/P5018
这道题其实就是用 hash 水过去的, 我们维护两个 hash
一个是先左子树后右子树的 h1
一个是先右子树后左子树的 h2
如果一个点, 他的左子树的 h1== 右子树的 h2
那么以这个点为根的树就是对称二叉树了
TIPS:hash 的顺序至关重要!
- #include<cstdio>
- #include<iostream>
- #include<cstring>
- #include<algorithm>
- #include<queue>
- #include<iostream>
- #define LL long long
- using namespace std;
- const int M=2e6+7,mod=19260817;
- int read(){
- int ans=0,f=1,c=getchar();
- while(c<'0'||c>'9'){if(c=='-') f=-1; c=getchar();}
- while(c>='0'&&c<='9'){ans=ans*10+(c-'0'); c=getchar();}
- return ans*f;
- }
- int n,ans=1;
- int l[M],r[M],h[M];
- LL v1[M],v2[M];
- void dfs(int x){
- if(l[x]!=-1){
- dfs(l[x]); h[x]+=h[l[x]];
- v1[x]=(v1[x]*2333+v1[l[x]]*233)%mod;
- }
- if(r[x]!=-1){
- dfs(r[x]); h[x]+=h[r[x]];
- v1[x]=(v1[x]*2333+v1[r[x]]*1007)%mod;
- v2[x]=(v2[x]*2333+v2[r[x]]*233)%mod;
- }
- if(l[x]!=-1) v2[x]=(v2[x]*2333+v2[l[x]]*1007)%mod;
- if(l[x]!=-1&&r[x]!=-1&&v1[l[x]]==v2[r[x]]) ans=max(ans,h[x]);
- }
- int main(){
- //freopen("1.txt","r",stdin);
- n=read();
- for(int i=1;i<=n;i++) h[i]=1,v1[i]=read(),v2[i]=v1[i];
- for(int i=1;i<=n;i++) l[i]=read(),r[i]=read();
- dfs(1);
- printf("%d\n",ans);
- return 0;
- }
- View Code
来源: http://www.bubuko.com/infodetail-3320067.html