## PT07A - Play with a Tree

no tags

Hey, ACRush and Jelly are playing a game ! Let take a look at its rule:

You are given a tree. Two players take turns cutting edges on a tree. Some nodes is on the "ground". When a player cuts an edge, all the edges that are no longer connected to the ground disappear. The player who can not take a move loses.

ACRush plays first. Both of them are very good players. If you know state of the tree they are playing with, can you guess who will win?

Node 4 is on the ground.

### Input

Input consists of multiple test-cases. The first line contains one integer t - number of cases (0 < t <= 20). For each case, the input format is following. The first line contains one integer N (1 <= N <= 100000). The next line N integers s[i] (1 or 0). If s[i] is 1, the i-th node is on the ground. If s[i] is 0, the i-th node is not on the ground. Each line of the following N - 1 lines contains two integers u, v. They denote there is an edge between node u and node v (1 <= u,v <= N).
There is no blank line after each case.

### Output

For each case, output who will win the game. If ACRush wins, output 1; otherwise, output 0 (Jelly wins).
There is no blank line after each case.

### Example

```Input:
1
4
0 0 0 1
1 2
2 3
2 4

Output:
1
```

hide comments
 Joshi Cordova Monroy: 2013-05-06 02:40:49 Does the input contain only one tree per test case ? And is it strictly a tree or can it contain loops ? Piyush Kapoor: 2012-05-15 17:49:16 Not at all an easy problem !!! Jonathan Schmidt-Dominé: 2011-12-04 20:32:29 “Some nodes is on the ‘ground’.” Does that mean that mean there is only one node on the ground, or many nodes? Rafa³ Bielenia: 2010-07-11 18:04:55 TL is too strict! Please fix it. Last edit: 2010-07-13 22:50:53

 Added by: Thanh-Vy Hua Date: 2007-04-07 Time limit: 0.100s Source limit: 50000B Memory limit: 1536MB Cluster: Cube (Intel G860) Languages: All except: ERL JS-RHINO NODEJS PERL6 VB.NET Resource: Co-author Amber