Problem A: Judgement [Easy I]

## Problem A: Judgement [Easy I]

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 2629  Solved: 604
[Submit][Status][Web Board]

## Description

Please judge whether the given tree is a heap.

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

• Shape property: a 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 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

[Submit][Status]