PT07A  Play with a Tree
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 testcases. 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 ith node is on the ground.
If s[i] is 0, the ith 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:
20130506 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:
20120515 17:49:16
Not at all an easy problem !!! 

Jonathan SchmidtDominé:
20111204 20:32:29
“Some nodes is on the ‘ground’.”


Rafa³ Bielenia:
20100711 18:04:55
TL is too strict!

Added by:  ThanhVy Hua 
Date:  20070407 
Time limit:  0.100s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO NODEJS PERL6 VB.NET 
Resource:  Coauthor Amber 