題目 2463:
信息學(xué)奧賽一本通T1557-祖孫詢問
時間限制: 2s
內(nèi)存限制: 192MB 提交: 74 解決: 27
題目描述
已知一棵 n 個節(jié)點的有根樹。有 m 個詢問，每個詢問給出了一對節(jié)點的編號 x 和 y，詢問 x 與 y 的祖孫關(guān)系。
輸入格式
輸入第一行包括一個整數(shù) n 表示節(jié)點個數(shù)；
接下來 n 行每行一對整數(shù)對 a 和 b 表示 a 和 b 之間有連邊。如果 b 是 ?1，那么 a 就是樹的根；
第 n+2 行是一個整數(shù) m 表示詢問個數(shù)；
接下來 m 行，每行兩個正整數(shù) x 和 y，表示一個詢問。
輸出格式
對于每一個詢問，若 x 是 y 的祖先則輸出 1，若 y 是 x 的祖先則輸出 2，否則輸出 0。
樣例輸入
10
234 -1
12 234
13 234
14 234
15 234
16 234
17 234
18 234
19 234
233 19
5
234 233
233 12
233 13
233 15
233 19
提示
數(shù)據(jù)范圍與提示：
對于 30% 的數(shù)據(jù)，1≤n,m≤103 ；
對于 100% 的數(shù)據(jù)，1≤n,m≤4×104 ，每個節(jié)點的編號都不超過 4×104 。