2018 T4 对称二叉树

主知识点：树与深搜。交叉标签：深搜、树、树形动态规划、哈希。
暴力标注：有直接镜像搜索解。
OJ 使用标准输入与标准输出。原比赛文件名为 tree.in / tree.out；下方如保留原文件约定，以本句的 OJ 约定为准。
时限 1 秒；内存 256 MiB；测试点 25；总分 100。
数据来源：官网数据；与公开存档逐文件一致。

题目描述

给出一棵带点权的有根二叉树。将所有节点的左右子树交换后，若对应位置的结构及点权均与原树相同，则称它对称。求最大的对称子树的节点数。以某节点为根的子树必须包含该节点和全部后代；单节点子树也对称。

输入格式

第一行一个正整数 $n$，表示给定的树的节点的数目，规定节点编号 $1 \sim n$，其中节点 $1$ 是树根。

第二行 $n$ 个正整数，用一个空格分隔，第 $i$ 个正整数 $v_i$ 代表节点 $i$ 的权值。

接下来 $n$ 行，每行两个正整数 $l_i, r_i$，分别表示节点 $i$ 的左右孩子的编号。如果不存在左 / 右孩子，则以 $-1$ 表示。两个数之间用一个空格隔开。

输出格式

输出文件共一行，包含一个整数，表示给定的树的最大对称二叉子树的节点数。

样例

样例 1

输入：

2 
1 3 
2 -1 
-1 -1

输出：

1

样例 2

输入：

10 
2 2 5 5 5 5 4 4 2 3 
9 10 
-1 -1 
-1 -1 
-1 -1 
-1 -1 
-1 2 
3 4 
5 6 
-1 -1 
7 8

输出：

3

数据范围与特殊性质

共 $25$ 个测试点。

$v_i \leq 1000$。

• 测试点 $1 \sim 3, n \leq 10$，保证根结点的左子树的所有节点都没有右孩子，根结点的右子树的所有节点都没有左孩子。

• 测试点 $4 \sim 8, n \leq 10$。

• 测试点 $9 \sim 12, n \leq 10^5$，保证输入是一棵“满二叉树”。

• 测试点 $13 \sim 16, n \leq 10^5$，保证输入是一棵“完全二叉树”。

• 测试点 $17 \sim 20, n \leq 10^5$，保证输入的树的点权均为 $1$。

• 测试点 $21 \sim 25, n \leq 10^6$。

本题约定：

层次：节点的层次从根开始定义起，根为第一层，根的孩子为第二层。树中任一节点的层次等于其父亲节点的层次加 $1$。

树的深度：树中节点的最大层次称为树的深度。

满二叉树：设二叉树的深度为 $h$，且二叉树有 $2^h-1$ 个节点，这就是满二叉树。

完全二叉树：设二叉树的深度为 $h$，除第 $h$ 层外，其它各层的结点数都达到最大个数，第 $h$ 层所有的结点都连续集中在最左边，这就是完全二叉树。

附加样例

本题的公开样例整理在对应的“样例”ZIP 中。样例不计入评测测试点；题面中的样例也已保留。

暴力退路标注（教学补充）

有直接镜像搜索解。枚举每个子树根，用成对 DFS 精确检查镜像结构与点权，可直接解决；简单总复杂度上界 O(n²)，随机/均衡数据常较快，不作为所有大规模数据的时间保证。小规模 1~8 点为 32%。树形 DP/哈希是另一条优化路线。

目标范围：小规模 32%；精确镜像检查可优化到实用解。部分分按原题规模判断，不构成对任意实现或评测机的得分保证。

来源与整理说明

题目原作者/发布者：中国计算机学会 CCF / NOI。题意经过改写，保留公式、输入输出、样例及约束；知识点和暴力标注为本次整理补充。

• 题面及约束校对来源：洛谷 CCF_NOI 题目 P5018
• 赛事：NOIP 普及组复赛（CSP-J 前身） 2018。
• 详细数据来源、版本和哈希见总包 来源与校验/manifest.json。