分析

一个非常自然的想法就是
枚举每个节点作为对称二叉树的根
然后左右遍历检查是否合格
最后取一个max

那么这个时间复杂度是多少呢
首先我们知道，若以为根节点
那么只有当左右子树大小相等时可以向下遍历
那么我们进而想，什么情况下
会有最多的可以遍历的根呢
当然就是完全二叉树的时候
因为一个点会被遍历，当且仅当根为其祖先
那么完全二叉树时，总共有个祖先
所以总的时间复杂度为：

代码

由于这道题是很久以前做的，码风比较清奇

#include<iostream>
#include<cstdio>
#include<cmath>
#include<queue>
#include<algorithm>
#include<cstring>
#include<string>
#define INF 0x7fffffff
#define LL long long
using namespace std;

const int MAXn=1e6+1;
LL Tree[MAXn][3],total;
LL sum[MAXn],val[MAXn];
LL x,y;
bool pd;

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

void Symmetric_tree(LL aa,LL bb)
{
    if(aa==-1 && bb==-1) return;
    if(aa==-1 || bb==-1 || val[aa]!=val[bb]){pd=false; return;}
    Symmetric_tree(Tree[aa][1],Tree[bb][2]);
    Symmetric_tree(Tree[aa][2],Tree[bb][1]);
} 

LL Count(LL p)
{
    LL num=0;
    if(Tree[p][1]!=-1) num+=Count(Tree[p][1]);
    if(Tree[p][2]!=-1) num+=Count(Tree[p][2]);
    return num+1;
}

int main()
{
    total=read();    
    for(int i=1;i<=total;i++) val[i]=read();
    for(int i=1;i<=total;i++)
    {
        Tree[i][0]=i;
        x=read();y=read();
        Tree[i][1]=x;Tree[i][2]=y;
    }
    LL ans=1;
    for(int i=1;i<=total;i++)
    {
        pd=true;
        if(Tree[i][1]!=-1 && Tree[i][2]!=-1 && val[Tree[i][1]]==val[Tree[i][2]])
        {
            Symmetric_tree(Tree[i][1],Tree[i][2]);
            if(pd) ans=max(ans,Count(i));
        }
    }
    printf("%lld",ans);
    return 0;
}