2021.08.09 P5018 对称二叉树（树形结构）

2021.08.09 P5018 对称二叉树（树形结构）

[P5018 NOIP2018 普及组] 对称二叉树 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题意：

求一棵子树，关于该子树根节点轴对称的节点数最大。

分析：

暴力。

代码如下：

40tps

#include<cstdio>

#include<iostream>

#include<algorithm>

using namespace std;

const int N=1e6+10;

int n,val[N],ans;

struct node{

	int l,r,flag,sum,val,size;

}a[N];

inline int read(){

	int s=0,w=1;

	char ch=getchar();

	while(ch<'0'||ch>'9'){

		if(ch=='-')w=-1;

		ch=getchar();

	}

	while(ch<='9'&&ch>='0'){

		s=s*10+ch-'0';

		ch=getchar();

	}

	return s*w;

}

void dfs(int x,int flag){

	//fa[x]=f;dep[x]=dep[fa[x]]+1;

	if(!x)return ;

	//a[x].flag=flag;a[x].val=val[x];

	//a[x].maxn=dep[x];

	a[x].flag=flag;

	a[x].sum=a[x].val=flag*a[x].val;

	//a[x].val直接读入

	a[x].size=1;

	dfs(a[x].l,1);dfs(a[x].r,-1);

	a[x].sum+=a[a[x].l].sum+a[a[x].r].sum;

	//a[x].maxn=max(a[x].maxn,max(a[a[x].l].maxn,a[a[x].r].maxn));

	a[x].size+=(a[a[x].l].size+a[a[x].r].size);

	if(a[x].sum==a[x].val&&a[a[x].l].size==a[a[x].r].size&&a[a[x].l].sum==-a[a[x].r].sum)ans=max(ans,a[x].size);

}

int main(){

	n=read();

	for(int i=1;i<=n;i++)a[i].val=read();

	for(int i=1;i<=n;i++){

		a[i].l=read();a[i].r=read();

		if(a[i].l==-1)a[i].l=0;

		if(a[i].r==-1)a[i].r=0;

		//cout<<i<<" "<<a[i].l<<" "<<a[i].r<<endl;

	}

	dfs(1,1);

	//for(int i=1;i<=n;i++)

	//cout<<i<<" l "<<a[i].l<<" r "<<a[i].r<<" flag "<<a[i].flag<<" val "<<a[i].val<<" size "<<a[i].size<<" sum "<<a[i].sum<<endl;

	cout<<ans;

	return 0;

}

100tps

#include<cstdio>

#include<iostream>

#include<algorithm>

using namespace std;

const int N=1e6+10;

int n;

struct node{

	int l,r,size,val;

}a[N];

inline int read(){

	int s=0,w=1;

	char ch=getchar();

	while(ch<'0'||ch>'9'){

		if(ch=='-')w=-1;

		ch=getchar();

	}

	while(ch<='9'&&ch>='0'){

		s=s*10+ch-'0';

		ch=getchar();

	}

	return s*w;

}

void dfs(int x){

	a[x].size=1;

	if(a[x].l)dfs(a[x].l),a[x].size+=a[a[x].l].size;

	if(a[x].r)dfs(a[x].r),a[x].size+=a[a[x].r].size;

}

bool check(int x,int y){

	if(!x&&!y)return true;

	if(x&&y&&a[x].val==a[y].val&&check(a[x].l,a[y].r)&&check(a[x].r,a[y].l))

	return true;

	return false;

}

int main(){

	n=read();

	for(int i=1;i<=n;i++)a[i].val=read();

	for(int i=1;i<=n;i++){

		a[i].l=read();a[i].r=read();

		if(a[i].l==-1)a[i].l=0;

		if(a[i].r==-1)a[i].r=0;

	}

	dfs(1);

	int ans=0;

	for(int i=1;i<=n;i++)if(check(a[i].l,a[i].r))ans=max(ans,a[i].size);

	cout<<ans;

	return 0;

}

2021.08.09 P5018 对称二叉树（树形结构）的相关教程结束。