求证明时间复杂度

#include<bits/stdc++.h>
using namespace std;
int n,a[1000005];
int res = 0;
int lc[1000005],rc[1000005],siz[1000005];
int dfs(int root) {
    siz[root]=1;
    if(lc[root] != -1)
        siz[root]+=dfs(lc[root]);
    if(rc[root] != -1)
        siz[root]+=dfs(rc[root]);
    return siz[root];
}
bool check(int u,int v) {
    if (u != -1 && v != -1)
    {
        if (a[u] != a[v]) return false;
        return check(lc[u], rc[v]) && check(rc[u], lc[v]);
    }
    else if (u == -1 && v == -1) return true;
    else return false;
}
void dfs1(int root)
{
    if (root == -1 || siz[root] < res) return;
    if (check(root, root)) res = max(res, siz[root]);
    dfs1(lc[root]);
    dfs1(rc[root]);
}
int main() {
    int i,j,k;
    cin>>n;
    for(i=1; i<=n; i++) scanf("%d", &a[i]);
    for(i=1; i<=n; i++) scanf("%d%d", &lc[i], &rc[i]);
    dfs(1);
    dfs1(1);
    printf("%d", res);
}