水是很重要的資源，沒有水的話人就活不下去。有一個都市仰賴著一個強大的水源，水源的水會經過很多個點，供應整個城市的運作。
有一天水利局發現有一部分的水被汙染了，只要上游汙染，下游就也會被汙染。他們派出稽查員隨機檢驗各個地點的水質，每次的評估都會預測污染的源頭應該是往回數的第 $k$ 個地點，也就是調查地點與污染源的距離為 $k$。由於預測也有可能會有錯，所以要綜合所有的資料找出最有可能的汙染源是哪個地點，但他們不太會分析這種事情，委託你來處理這個問題。
他們給你了整個城市的水路圖，共有 $n$ 個地點，每個地點會被編號為 $1$ ~ $n$ 。除了源頭之外，每個地點的水只有一個來源，也就是整個水路圖會從源頭一直分支，不會匯流。接著他們將調查結果給你，一個地點被預測最多次就最有可能是汙染源，請找出最有可能的汙染源。
輸入只有一筆測資，
第一行有一個數字 $n$($1 \le n \le 10^5$)，代表地點的數量
接下來有 $n$ 行，每一行有兩個數字 $a$ 與 $b$($1 \le a, b \le n$)，代表 $a$ 點往上游走的第一個地點是 $b$ 點。
若 $a$ 跟 $b$ 一樣，代表 $a$ 就是全部的水源
接下來有一個數字 $q$ ($1 \le q \le 10^4$)，代表調查的數量。
再來有 $q$ 行，每一行有兩個數字 $p$ 與 $k$ ($1 \le p \le n, 0 \le k \le n$)，代表調查的地點與預測的汙染源距離。
輸出最有可能是汙染源的地點，若不只一個點可能是汙染源，則將所有可能的汙染源地點從小到大輸出，用空白隔開。
8 1 6 2 2 3 2 4 3 5 3 6 7 7 2 8 5 5 8 2 4 1 3 1 1 3 8 0
2 3
60% $n \le 1000$, $q \le 100$
100% $n \le 100000$, $q \le 10000$
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」 |
|||||