e330: NOIP2018 4.对称二叉树
Tags :
Accepted rate : 3人/4人 ( 75% ) [非即時]
評分方式:
Tolerant

最近更新 : 2019-07-19 19:50

Content

一棵有点权的有根树如果满足以下条件,则被轩轩称为对称二叉树:

  1. 二叉树;
  2. 将这棵树所有节点的左右子树交换,新树和原树对应位置的结构相同且点权相等。

现在给出一棵二叉树,希望你找出它的一棵子树,该子树为对称二叉树,且节点数最多。请输出这棵子树的节点数。

注意:只有树根的树也是对称二叉树。本题中约定,以节点 T 为子树根的一棵“子树”指的是:节点T 和它的全部后代节点构成的二叉树。

Input

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

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

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

Output

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

Sample Input
2 
1 3 
2 -1 
-1 -1 

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
Sample Output
1

3
測資資訊:
記憶體限制: 256 MB
公開 測資點#0 (4%): 1.0s , <50M
公開 測資點#1 (4%): 1.0s , <1K
公開 測資點#2 (4%): 1.0s , <1K
公開 測資點#3 (4%): 1.0s , <1K
公開 測資點#4 (4%): 1.0s , <1K
公開 測資點#5 (4%): 1.0s , <1K
公開 測資點#6 (4%): 1.0s , <1K
公開 測資點#7 (4%): 1.0s , <1K
公開 測資點#8 (4%): 1.0s , <1K
公開 測資點#9 (4%): 1.0s , <1M
公開 測資點#10 (4%): 1.0s , <1M
公開 測資點#11 (4%): 1.0s , <1M
公開 測資點#12 (4%): 1.0s , <1M
公開 測資點#13 (4%): 1.0s , <1M
公開 測資點#14 (4%): 1.0s , <1M
公開 測資點#15 (4%): 1.0s , <1M
公開 測資點#16 (4%): 1.0s , <1M
公開 測資點#17 (4%): 1.0s , <10M
公開 測資點#18 (4%): 1.0s , <10M
公開 測資點#19 (4%): 1.0s , <10M
公開 測資點#20 (4%): 1.0s , <10M
公開 測資點#21 (4%): 1.0s , <50M
公開 測資點#22 (4%): 1.0s , <50M
公開 測資點#23 (4%): 1.0s , <50M
公開 測資點#24 (4%): 1.0s , <50M
Hint :

【数据规模与约定】
共 25 个测试点。
vi1000
测试点 13,n10,保证根结点的左子树的所有节点都没有右孩子,根结点的右 子树的所有节点都没有左孩子。
测试点 48,n10
测试点 912,n10^5,保证输入是一棵“满二叉树” 。
测试点 1316,n10^5,保证输入是一棵“完全二叉树”。
测试点 1720,n10^5,保证输入的树的点权均为 1
测试点 2125,n10^6

Tags:
出處:
NOIP2018普及组第三题 [管理者:
liouzhou_101 (王启圣)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」