对称二叉树

首先考虑最暴力的暴力，那就是对于每颗子树都检验一次，然后求一个最大值，那么这个时间复杂度大约是 的，所以考虑优化检验方式
那么主要就是看 函数的实现了

bool Check(int L,int R)
{
    if (L == -1 && R == -1)return 1;
    return (L != -1 && R != -1 && V[L] == V[R] && 
            Check(Son[L][1],Son[R][2]) && Check(Son[L][2],Son[R][1]));
}

那么对于完全二叉树，显然这个函数每次最多会向下跳 次，
如果不是完全二叉树，显然它能跳的次数就更少了，因为又特别强有力的权值剪枝和子树大小剪枝
最后，如果返回的是 true 那么就可以用这个子树的 size 去更新一下答案好像就可以了
所以总时间复杂度为

#include <cstdio>
#define max(a, b) (a > b ? a : b)

using namespace std;

const int Maxn = 1e6+10;
int N, V[Maxn], Son[Maxn][3];
int Size[Maxn], Ans(1);

inline int Read()
{
    int X(0), T(1);
    char O = getchar();
    while (O < '0' || O >'9')
    {
        if (O == '-')T = -1;
        O = getchar();
    }
    while (O >= '0' && O <= '9')
    {
        X = (X << 1) + (X << 3) + (O ^ 48);
        O = getchar();
    }
    return X * T;
}

bool Check(int L, int R)
{
    if (L == -1 && R == -1)return 1;
    return (L != -1 && R != -1 && V[L] == V[R] && Check(Son[L][1],Son[R][2]) && Check(Son[L][2],Son[R][1]));
}

int DFS(int X)
{
    Size[X] = 1;
    if (Son[X][2] == -1 && Son[X][1] == -1)return Size[X];
    if (Son[X][1] > 0)Size[X] += DFS(Son[X][1]);
    if (Son[X][2] > 0)Size[X] += DFS(Son[X][2]);
    if (Size[Son[X][1]] != Size[Son[X][2]] || V[Son[X][1]] != V[Son[X][2]])return Size[X];
    if(Check(Son[X][1], Son[X][2]))Ans = max(Ans, Size[X]);
    return Size[X];
}

int main()
{
    N = Read();
    for (int i = 1; i <= N; ++i)V[i] = Read();
    for (int i = 1; i <= N; ++i)Son[i][1] = Read(), Son[i][2] = Read();
    DFS (1);
    printf ("%d\n",Ans);
    return 0;
}