洛谷5018 对称二叉树

题意

对于一棵二叉树，如果它所有节点的左右子树交换后和原树一样，那么称它为对称二叉树。

给出一棵 $n(\le 10^6)$ 个节点的二叉树，求它所有对称子树中节点个数的最大值。

题解

可以发现，如果一个节点 $x$ 的左子树的 左->中->右 遍历和右子树的 右->中->左 遍历相同，那么以 $x$ 为根的子树就是棵对称二叉树。

所以对于一个点，维护以它为根的子树的两种遍历方式的hash值。同时维护子树大小 $siz[]$ ，如果它是对称二叉树就用它更新答案的最大值。

注意hash值乘的数要足够大，否则会出锅。

#include<bits/stdc++.h>
#define ull unsigned long long

using namespace std;

inline int read()
{
    char ch=getchar(); int f=1,x=0;
    while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
    while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
    return f*x;
}

const int N=1000005;
const ull A=999999751,B=299999827,C=100000007,ha=89999794200117649;
ull hs1[N],hs2[N];
int n,ans=1,v[N],lson[N],rson[N],siz[N];

void dfs(int x)
{
    if (lson[x]) dfs(lson[x]);
    if (rson[x]) dfs(rson[x]);
    siz[x]=siz[lson[x]]+siz[rson[x]]+1;
    if (siz[lson[x]]==siz[rson[x]] && hs1[lson[x]]==hs2[rson[x]]) ans=max(ans,siz[x]);
    hs1[x]=(hs1[lson[x]]*A+v[x]*B+hs1[rson[x]]*C)%ha; //左中右
    hs2[x]=(hs2[rson[x]]*A+v[x]*B+hs2[lson[x]]*C)%ha; //右中左
}

signed main()
{
    n=read();
    for (int i=1;i<=n;i++) v[i]=read();
    for (int i=1;i<=n;i++)
    {
        lson[i]=read(); if (lson[i]==-1) lson[i]=0;
        rson[i]=read(); if (rson[i]==-1) rson[i]=0;
    }
    dfs(1);
    return !printf("%d",ans);
}