P5018 对称二叉树

题面:https://www.luogu.org/problem/P5018

本题直接写一个树上hash水过。。。
Code:
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<queue>
#include<vector>
#include<map>
#define ull unsigned long long
using namespace std;
const int N=1000005;
ull base1=999999751,base2=299999827,base3=100000007,md=89999794200117649ll;
ull hasel[N],haser[N],val[N],ans,size[N];
int n,lson[N],rson[N];
void dfs(int x,int fa){
    if(lson[x]){
        dfs(lson[x],x);
    }
    if(rson[x]){
        dfs(rson[x],x);
    }
    size[x]=size[lson[x]]+size[rson[x]]+1;
    if(size[lson[x]]==size[rson[x]] && hasel[lson[x]]==haser[rson[x]]){
        ans=max(ans,size[x]);
    }
    hasel[x]=hasel[lson[x]]*base1+val[x]*base2+hasel[rson[x]]*base3;
    hasel[x]%=md;
    haser[x]=haser[rson[x]]*base1+val[x]*base2+haser[lson[x]]*base3;
    haser[x]%=md;
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>val[i];
    }
    for(int i=1;i<=n;i++){
            int x,y;
            cin>>x>>y;
            if(x!=-1){
                lson[i]=x;
            }
            if(y!=-1){
                rson[i]=y;
            }
        }
    dfs(1,-1);
    cout<<ans<<endl;
    return 0;
}

P5018 对称二叉树

原文：https://www.cnblogs.com/ukcxrtjr/p/11649811.html