题目大意:问一棵有根带权二叉树中最大的对称二叉树子树,对称二叉树为需满足将这棵树所有节点的左右子树交换,新树和原树对应位置的结构相同且点权相等。
题解:在对称二叉树中,对于深度相同的两个节点$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;
}