回『原創/不分類題庫』
b326. 計畫巧遇
標籤 : 圖論
通過比率 : 23人/28人 ( 82% ) [非即時]
評分方式：
Tolerant

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

內容

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

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

Problem

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

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

輸入說明

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

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

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

輸出說明

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

每組測資後空一行。

範例輸入 #1 
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
範例輸出 #1 
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
提示 ：
標籤:
圖論
出處:
蘿莉控 [管理者： morris1028 (碼畜) ]

本題狀況 本題討論 排行

編號 身分 題目 主題 人氣 發表日期
沒有發現任何「解題報告」