[数据结构与算法]【luogu P5018】【NOIP2018pjT4】对称二叉树【DFS】

题目链接：对称二叉树

分析

枚举每个节点作为根。判断这棵树是否对称。

对于每个左儿子右儿子，每次递归左儿子的左儿子，右儿子的右儿子；左儿子的右儿子，右儿子的左儿子。
如果两个都是-1，那么贡献为0，但还是有对称性。
然后从结构，权值两个来判断对称性，每一对的贡献都是2，否则整棵树都不对称，标记一下并返回。
最后把所有有答案的树求max

上代码

这个NOIP如果没有摆渡车撑场就要变水题大会??
又是3年前的愿望

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;

int n,a[1000001],l[1000001],r[1000001];
int ans=1,ff=0;

int dfs(int x,int y,int sz)
{
	if(x==-1&&y==-1) return 0;
	if((x==-1||y==-1)&&x!=y)
	{
		ff=1;
		return 0;
	}
	if(a[x]!=a[y])
	{
		ff=1;
		return 0;
	} 
	return dfs(l[x],r[y],2)+dfs(l[y],r[x],2)+sz;
}

int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
	}
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d",&l[i],&r[i]);
	}
	for(int i=1;i<=n;i++)
	{
		int s=dfs(l[i],r[i],3);
		if(ff==0&&s>ans) ans=s; 
		ff=0;
	} 
	cout<<ans;
	return 0;
 }