[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;

}

巴特西

[NOIP2018 PJ T4]对称二叉树

最新文章

热门文章