1272 . The Agency
TopCoder
Description
原題目 請按這裡觀看題目。
以下是翻譯：
有一個有 n 個代理人(包括組長)的情報組織，而代理人的編號從 1 編號到 n.
很特別的是，他們的組織結構長得像一棵根固定的樹，而編號 1 號的組長一定在根的位置。
有時候，頑固的狗仔隊會試著向員工打聽訊息，而保密的最好方式就是透露假消息。
然而，如果員工們一直透露假消息，狗仔們就會因此反轉訊息得到真正的機密！
所以員工們就需要有時透露真實的消息有時透露假的消息，讓狗仔們被虛虛實實實實虛虛搞的團團轉！
當然，改變訊息的真假必須要做的讓狗仔們看不出來，而員工們的暗號就是打噴嚏（sneeze）。
隨著一個員工的動作，他自己、自己的下級、自己的下級的下級....
就會改變自己透露的訊息（真變假、假變真）
（注意：所有員工一開始都是透露真實的訊息）
而你是一個精明的狗仔，你發現了這個秘密，因此你密集地觀察到了每個員工的暗號，你能以此做為依據，
判斷某個員工說的情報是真是假嗎？
Input Format
第 1 行有兩個整數 n , m ，分別代表有幾位員工以及有幾個動作（打噴嚏或查詢）
(1 <= n,m <= 100,000)
接下來共有 n 行，有多個整數，分別代表第 i 個員工的下級
第一個整數 k 代表該員工有幾位下級
接著跟著 k 個整數，代表該員工的下級
接下來共有 m 行，代表查詢或動作
每行有兩個整數 a,b
若a=0，代表編號b的員工打了一個噴嚏
若a=1，代表你要查詢編號為b的員工說的情報是真是假
Output Format
針對a=1的情況輸出該員工目前的情形
若他說的情報是假消息 請輸出 1
若他說的情報是真情報 請輸出 0
Sample Input 1
5 7
1 2
2 5 4
0
0
1 3
1 4
0 2
0 4
1 5
0 1
0 3
1 3
1 2
2 5 4
0
0
1 3
1 4
0 2
0 4
1 5
0 1
0 3
1 3
Sample Output 1
0
1
1
1
1
Hints
Problem Source
原TIOJ1272 / INOI 2008
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 10 |
| 2 | 1 | 10 |
| 3 | 2 | 10 |
| 4 | 3 | 10 |
| 5 | 4 | 10 |
| 6 | 5 | 10 |
| 7 | 6 | 10 |
| 8 | 7 | 10 |
| 9 | 8 | 10 |
| 10 | 9 | 10 |