12821282 SUSTech Online Judge
Problem 1282 --Judgement [Easy II]

1282: Judgement [Easy II]

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 657  Solved: 205
[Submit][Status][Web Board]

Description

Please judge whether the given tree is a binary heap.

A binary heap is defined as a binary tree with two additional constraints:

  • Shape property: a binary heap is a complete binary tree
  • Heap property: the value stored in each node is either greater than or equal to \((\ge)\) or less than or equal to \((\le)\) the the values in the node's children

Input

The first line will be an integer T,which is the number of test cases.\((1\le T\le 10)\) For each test case, the first line will be an integer \(n\) \((1\le n\le 10^5)\).

The second line will be \(n\) integers,\(a_1,a_2,\cdots, a_n\),\((1\le a_i\le 10^9)\). \(a_i\) represents the value of the i-th node, then followed by \(n-1\) lines, each line will be two integers \(x\) and \(y\), which means y-th node is a child of x-th node. Besides, The left child will appear first (The order of appearance of child nodes is from left to right).  

Output

For each test, print the number of the test cases first, then print YES when the tree is a binary heap, else print NO.

We guarantee that \(1\le x,y\le n\) and input is a tree.

Sample Input

3
4
1 2 3 4
3 1
3 4
3 2
3
2 1 3
2 1 
2 3
3
2 1 3
3 1
3 2

Sample Output

Case #1: NO
Case #2: YES
Case #3: YES

HINT

Source

[Submit][Status]