#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e6+10;
struct trnode{LL l,r,c;}tr[N];
bool query(LL lc,LL rc)
{
    if(lc==-1&&rc==-1)return 1;
    if(lc==-1||rc==-1||tr[lc].c!=tr[rc].c)return 0;
    if(query(tr[lc].l,tr[rc].r)&&query(tr[lc].r,tr[rc].l))return 1;
    return 0;
}
LL sum(LL now)
{
    if(now==-1)return 0;
    else return sum(tr[now].l)+sum(tr[now].r)+1;
}
int main()
{
    LL n,ans=0;scanf("%lld",&n);
    for(LL i=1;i<=n;i++)scanf("%lld",&tr[i].c);
    for(LL i=1;i<=n;i++)scanf("%lld%lld",&tr[i].l,&tr[i].r);
    for(LL i=1;i<=n;i++)if(query(tr[i].l,tr[i].r))ans=max(ans,sum(i));
    printf("%lld",ans);
    return 0;
}

前言

这么简单的 T4。

思路

只需要判断每个节点的子树是否为对称二叉树，然后计算该子树的节点个数就行了。

怎么判断是否为对称二叉树呢？先看一个图。

当到节点 $x$ 时，需要满足 $v_{l_x}=v_{r_x}$。到节点 $y$ 和 $z$ 时，需要满足 $v_{l_y}=v_{r_z}$ 和 $v_{r_y}=v_{l_z}$。若其中 $l,r$ 其中一个的值为 $-1$ 或 $v$ 不相等，那么它就不是对称二叉树。

AC 代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int n,v[N],l[N],r[N],son[N];
bool dfs(int x,int y){
	if(x==-1&&y==-1) return true;//都是叶子节点时满足条件
	if(x==-1||y==-1) return false;//其中一个为叶子节点不满足
	if(v[x]!=v[y]) return false;//v值不同不满足
	return dfs(l[x],r[y])&&dfs(r[x],l[y]);
}
int count(int x){
	if(x==-1) return 0;
	son[x]=count(l[x])+count(r[x])+1;
	return son[x];
}
int main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&v[i]);
	for(int i=1;i<=n;i++) scanf("%d%d",&l[i],&r[i]);
	count(1); //计算子树的节点个数
	int sum=0;
	for(int i=1;i<=n;i++) if(dfs(i,i)) sum=max(sum,son[i]);
	printf("%d\n",sum);
	return 0;
}