b326: 計畫巧遇
Tags : 圖論
Accepted rate : 14人/17人 ( 82% ) [非即時]
評分方式:
Tolerant

最近更新 : 2014-10-02 20:48

Content

正陷入暗戀的蘿莉控,對象正是那小海女 “能年犬”,為了與其相遇,做了一個情報偵測器,但總不能刻意繞道去相遇,這顯然會相當接近跟蹤狂。根據情報網顯示,地圖將會長得跟樹狀圖一樣,接著會有一連串的消息顯示小海女疑似出現的地方,同時也會被驗證是假消息。

能年犬

蘿莉控只想知道如果從 x 點回到家的路上,有沒有機會遇到小海女。如果事先知道將會在哪個場所相遇,就能事先準備。接下來就請你協助他了!

Problem

給定一棵樹,樹根編號 0,每個點一開始的權重為 0,操作有以下兩種。

操作 M x : 將節點 x 的權重從 0->1 或者 1->0。
操作 S x : 輸出從 x 到 root 路徑上,第一個權重為 1 的節點編號。

Input

輸入有多組測資,每組測資第一行會有一個整數 N (N < 32767),表示這棵樹有多少個節點。

接下來會有 N - 1 行,每一行上會有兩個整數 u, v (0 <= u, v < N) 表示 u, v 之間有一條邊。

接下來會有一行上有一個整數 Q (Q < 32767),表示接下來有 M 組詢問。

Output

對於每個詢問結果輸出一行,請參照範例輸出的說明。

每組測資後空一行。

Sample Input
10
0 1
0 2
1 3
0 4
3 5
4 6
5 7
5 8
4 9
10
M 1
S 8
S 4
M 0
M 7
M 9
S 5
M 3
M 8
S 5

31
0 1
0 2
0 3
1 4
1 5
2 6 
2 7
3 8
4 9
4 10
4 11
6 12
6 13
12 14
12 15
13 16
13 17
14 18
14 19
14 20
17 21
17 22
20 23
21 24
21 25
22 26
22 27
23 28
24 29
24 30
10
M 6
S 29
S 9
M 0
S 9
S 6
S 2
M 6
S 29
S 6
Sample Output
1
-1
1
3

6
-1
0
6
0
0
0
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (50%): 1.0s , <1M
公開 測資點#1 (30%): 1.0s , <1M
公開 測資點#2 (20%): 1.0s , <10M
Hint :
Tags:
圖論
出處:
蘿莉控 [管理者:
morris1028 (碼畜)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」