$P5018 对称二叉树$

problem

一直忘记给这个题写题解了。

这题挺水的吧。

挺后悔当时没写出来。

#ifdef Dubug

#endif

#include <bits/stdc++.h>

using namespace std;

typedef long long LL ;

inline LL In() { LL res(0),f(1); register char c ;

	while(isspace(c=getchar())) ; c == '-'? f = -1 , c = getchar() : 0 ;

	while(res = (res << 1) + (res << 3) + (c & 15) , isdigit(c=getchar())) ;

	return res * f ;

}

int n ;

const int N = 1e6 + 5 ;

int a[N] ;

int Left[N] , Right[N] ;

int sum = 1 ;

inline bool dfs(int x,int y) {//搜索能否有对称。

	if(x == -1 and y == -1) return 1 ;

	if(x == -1 or y == -1 or a[x] != a[y]) return 0 ;

	sum += 2 ;

	return (dfs(Left[x],Right[y]) and dfs(Left[y],Right[x])) ;

}

signed main() {

	n = In() ;

	for(register int i=1;i<=n;i++) a[i] = In() ;

	for(register int i=1;i<=n;i++) Left[i] = In() , Right[i] = In() ;

	int ans = -0x7f ;

	for(register int i=1;i<=n;i++) {//每个枚举一遍。n个节点。

		sum = 1 ;//初始化

		if(dfs(Left[i],Right[i])) ans = max(ans,sum) ;//如果有对称 那么更新ans

	}

	cout << ans << endl ;

	return 0 ;

}

巴特西

$P5018 对称二叉树$

最新文章

热门文章