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 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’.”
|
|
Rafa³ Bielenia:
2010-07-11 18:04:55
TL is too strict!
|
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 |