分析
也没什么好说的。看个图。
对于一个节点来说,如果他对称,那么他的每一个节点都一一对应。
于是只要跑一遍每一个点及其子树,判断一下每个节点与其对应的节点是否相等(值相等,且子树大小相等)就行了代码
#include<bits/stdc++.h> #define ls(u) ch[0][u] #define rs(u) ch[1][u] using namespace std; const int N=1e6+10; int n,ans,tot; int v[N],ch[2][N],siz[N]; inline void dfs(int now) { if(now==-1) return ; siz[now]=1; dfs(ls(now)),dfs(rs(now)); siz[now]+=siz[ls(now)]+siz[rs(now)]; } inline bool check(int x,int y) { if(x==-1&&y==-1) return 1; if(x==-1||y==-1) return 0; if(siz[x]!=siz[y]) return 0; if(v[x]!=v[y]) return 0; if(check(ch[0][x],ch[1][y])&&check(ch[1][x],ch[0][y])) return 1; return 0; } int main() { scanf("%d",&n); for (int i=1;i<=n;i++) scanf("%d",&v[i]); for (int i=1;i<=n;i++) scanf("%d%d",&ls(i),&rs(i)); dfs(1); for (int i=1;i<=n;i++) if(check(ch[0][i],ch[1][i])) ans=max(ans,siz[i]); printf("%d\n",ans); return 0; }