[NOIP2018 PJ T4]对称二叉树

题目大意：问一棵有根带权二叉树中最大的对称二叉树子树，对称二叉树为需满足将这棵树所有节点的左右子树交换，新树和原树对应位置的结构相同且点权相等。

题解：在对称二叉树中，对于深度相同的两个节点$u,v$，必定有$ls(u)=rs(v)$，$rs(u=ls(v)$，并且$val(u)=val(v)$，对每个点跑一遍深搜就可以了。发现跑一个点最多遍历它子树中较少的一棵子树。复杂度为$O(n\log_2n)$

卡点：无

 

C++ Code：

#include <iostream>
#define maxn 1000010
#define ls(u) son[0][u]
#define rs(u) son[1][u]
int N, n, ans;
int V[maxn], son[2][maxn], sz[maxn];
bool check(int u, int v) {
	if (!~u && !~v) return true;
	if (~u && ~v && V[u] == V[v] && check(ls(u), rs(v)) && check(rs(u), ls(v))) return true;
	return false;
}
void dfs(int u) {
	sz[u] = 1;
	if (~ls(u)) dfs(ls(u)), sz[u] += sz[ls(u)]; 
	if (~rs(u)) dfs(rs(u)), sz[u] += sz[rs(u)]; 
}
int main() {
	std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);
	std::cin >> n;
	for (int i = 1; i <= n; ++i) std::cin >> V[i];
	for (int i = 1; i <= n; ++i) std::cin >> ls(i) >> rs(i);
	dfs(1);
	for (int i = 1; i <= n; ++i)
		if (check(ls(i), rs(i))) ans = std::max(ans, sz[i]);
	std::cout << ans << '\n';
	return 0;
}