公園散步

View as PDF

Submit solution


Points: 100 (partial)
Time limit: 7.0s
Memory limit: 64M

Author:
Problem type

小憐和小龍是一對好朋友,他們喜歡相約到一個特別的公園散步。
這個公園的地圖是一棵樹,亦即有 \(n\) 個點,每個點間有些有道路相接,使得從任一個點都有唯一的路徑到另一個點,可以證明一共會有 \(n-1\) 條道路。
而樹上兩點的距離被定義為從某點要經過幾條道路才會到另一個點。
小憐很怕狗,每當他在某個點看到狗時,他會馬上跑到公園中離該地最遠的點。
心急的小龍會想問你小憐跑到了多遠的地方去,他一共會問你 \(Q\) 次。


Input

輸入第一行是一個 \(n\)。
接著是 \(n-1\) 行的 \(u,v (1\leq u,v \leq n)\),代表 \(u,v\) 間有一條邊。
接著是一行一個數 \(Q\),代表有 \(Q\) 筆詢問。
接著有 \(Q\) 行個一個數字 \(k\),代表小龍想知道在點 \(k\) 小憐跑掉會跑多遠的距離。

Output

對於每個詢問,輸出一行一個整數代表答案。

Constraints

第 \(1\) 組測資 \(n\leq 10\),\(Q=1\),圖中存在一個點和其他點都連接。

第 \(2\) 組測資 \(n\leq 10\),\(Q=1\),圖是一條鍊。

第 \(3\) 組測資 \(n\leq 20\),\(Q \leq 20\)。

第 \(4\) 組測資 \(n\leq 10^5\),\(Q=1\)。

第 \(5\) 組測資 \(n\leq 10^5\),\(Q\leq 10^5\)。

Sample Input
5
1 5
1 2
2 3
2 4
5
1
2
3
4
5
Sample Output
2
2
3
3
3

Comments

There are no comments at the moment.