Problem Background

NOIP2018 Junior Group T4

Problem Description

A rooted tree with node weights is considered symmetric by Xuan if it meets the following conditions:

1. It is a binary tree.
2. After swapping the left and right subtrees of all nodes in the tree, the new tree has the same structure and equal node weights at corresponding positions as the original tree.

In the diagram below, the numbers inside the nodes represent the weights, and the $id$ outside the nodes represent the node numbers.

Given a binary tree, you are asked to find a subtree that is a symmetric binary tree and has the maximum number of nodes. Output the number of nodes in this subtree.

Note: A tree with only the root node is also considered a symmetric binary tree. In this problem, a "subtree" rooted at node $T$ refers to the binary tree consisting of node $T$ and all its descendant nodes.

Input Format

The first line contains a positive integer $n$, representing the number of nodes in the given tree. Node numbers are specified as $1 \sim n$, with node $1$ being the root.

The second line contains $n$ positive integers separated by spaces, where the $i$-th positive integer $v_i$ represents the weight of node $i$.

The next $n$ lines each contain two positive integers $l_i$ and $r_i$, representing the left and right child node numbers of node $i$, respectively. If a left or right child does not exist, $-1$ is used to indicate this. The two numbers are separated by a space.

Output Format

The output file consists of a single line containing an integer, which represents the number of nodes in the largest symmetric binary subtree of the given tree.

Sample Input and Output

Input Sample #1

2
1 3
2 -1
-1 -1

Output Sample #1

1

Input Sample #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

Output Sample #2

3

Notes

Sample 1 Explanation

The largest symmetric binary subtree is the one rooted at node $2$, with $1$ node.

Sample 2 Explanation

The largest symmetric binary subtree is the one rooted at node $7$, with $3$ nodes.

Data Size and Constraints

There are a total of $25$ test cases.

$v_i ≤ 1000$.

• Test cases $1 \sim 3, n ≤ 10$, ensuring that all nodes in the left subtree of the root have no right child, and all nodes in the right subtree of the root have no left child.
• Test cases $4 \sim 8, n ≤ 10$.
• Test cases $9 \sim 12, n ≤ 10^5$, ensuring that the input is a "full binary tree".
• Test cases $13 \sim 16, n ≤ 10^5$, ensuring that the input is a "complete binary tree".
• Test cases $17 \sim 20, n ≤ 10^5$, ensuring that all node weights in the input tree are $1$.
• Test cases $21 \sim 25, n ≤ 10^6$.

This problem defines:

• Level: The level of a node starts from the root, which is the first level, and the children of the root are the second level. The level of any node in the tree is one more than the level of its parent node.
• Depth of the tree: The maximum level of any node in the tree is called the depth of the tree.
• Full binary tree: If the depth of the binary tree is $h$ and the tree has $2^h-1$ nodes, it is a full binary tree.

• Complete binary tree: If the depth of the binary tree is $h$, all levels except the $h$-th level are filled to their maximum capacity, and all nodes at the $h$-th level are consecutively concentrated on the left side, it is a complete binary tree.

见题面 Input 部分

见题面 Output 部分