1307 . 世外魔島
TopCoder
Description
在魔王島上有很多座城市，城市裡面有很多區域以及各式各樣的人。
像是
1. 很威的蕃茄
2. 專門騙詐欺師的詐欺師
3. 沒有炎術才能的風術師
4. 常常穿得全身黑然後戴著大防風眼鏡旁邊還跟著一隻蟲的傢伙
5. 綠色頭髮喜歡吃披薩而且永遠打不死的魔女
6. 戴著拔不下來面具的傢伙
7. 每天讓有貓咪過敏症的主人過敏的貓
8. 整天拿相機拍天空的紙片人
(以上依照強度排序)
但是絕對不會有
1. 沒有中線的藝人
2. 奇怪的郭宗昇
3. 到處亂踢的紅鳥
(以上依照弱度排序)
魔王島上的人都很善良而且隨和，
他們也常常找人約個地方兩兩研究學術或切磋武藝，
不過到底要約在哪裡卻是個令人頭痛的問題，
七瀨認為如果能夠選擇一個對兩個人來說都近的地點的話應該會很不錯，
於是，作為能夠住在魔王島上的條件，
你被要求寫一個程式來找出兩個區域的最短路徑上的中間點。
值得一提的是，魔王島上的每個城市都可以用一棵無向的樹來表示。
Input Format
第一行有個整數 C 代表有幾個城市的人要請你幫忙。
每個城市的詢問資料裡面第一行有個兩個整數 N Q 代表城市內的區域數量、請你幫忙的人數。(1<=N<=10000)
接著N-1行每行有兩個數字 u v 代表u,v之間有一條直接相通的道路。
接下來 Q 行每行的四項資料則分別代表詢問人的名字、詢問人目前所在的區域、他約的人的名字、他約的人所在的區域。
魔王島上城市裡的區域編號都是由 0 一直到 N-1，而且每個人個名字都是由英文字母或數字構成，長度都不超過1000個字。
Output Format
請自行參照 Sample Output，
不過如果有多個區域符合條件的話請由小到大輸出。
Sample Input 1
6 2
0 1
0 3
2 3
2 4
2 5
lulu 4 cc 5
cat 0 dog 5
13 4
0 1
0 2
1 3
1 4
4 8
4 9
8 12
2 5
2 6
2 7
6 10
6 11
FarmerJohn 1 Bessie 12
Akira 2 Akiha 11
Nanase 5 Nagase 5
Daisuke 3 Shiika 2
Sample Output 1
cat and dog: 2 3
FarmerJohn and Bessie: 4 8
Akira and Akiha: 6
Nanase and Nagase: 5
Daisuke and Shiika: 0 1
Hints
Akira: 為啥這漫畫是限制級的啊 Orz
Problem Source
原TIOJ1307 / [TIOJ] IOI2008 暖身賽 2(prob G)。Problem Setter：akira。
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 11 |
| 2 | 1 | 11 |
| 3 | 2 | 11 |
| 4 | 3 | 11 |
| 5 | 4 | 11 |
| 6 | 5 | 11 |
| 7 | 6 | 11 |
| 8 | 7 | 11 |
| 9 | 8 | 12 |