TopCoder

User's AC Ratio

90.9% (10/11)

Submission's AC Ratio

33.3% (13/39)

Tags

Description

有天H.C.去便利商店買個食物,突然就被傳送到了異世界,什麼都不知道的他只好在路上閒逛。
突然,有個路人衝了過來,H.C.閃避不及被撞倒在地,經過一番詢問才知道那位旅人正在計算這個王國城市中的路徑數,所以才高速的在路上衝刺,閒閒沒事的H.C.打算幫忙他做這件事,可是他發現他手邊沒有電腦,只好請你幫忙寫份程式計算。
異世界的王國很特別,總共有$N$個城市卻只有$N-1$條道路,但仍保證任兩個城市可以互相到達,而你的目標則是回答對於一個城市$K$,有幾組路徑$(u, v)$在走最短路徑時會經過$K$。
異世界的居民不會將起點等於終點視為一條路徑。

Input Format

第一行輸入兩個數字$N , K$ $( 2 \le N \le 10 ^ 6 )$
接著輸入$N - 1$行 每行有兩個數字$ a , b $ $(1 \le a,b \le N)$
代表$ a $城市與$ b $城市之間有一條道路連通

Output Format

請輸出城市$K$有幾組路徑$(u, v)$在走最短路徑時會經過$K$

Sample Input

Sample Input #1
5 2
1 4
1 2
2 3
2 5

Sample Input #2
4 1
1 2
2 3
3 4

Sample Output

Sample Output #1
18

Sample Output #2
6

Hints

子任務(測資)額外限制分數
1(0~2)$N \le 10 ^ 3$20
2(3~5)$N \le 10 ^ 5$30
3(6~8)50



Sample #1 最短路徑會經過城市2的路徑為(4,3),(4,5),(1,3),(1,5),(3,1),(3,4),(3,5),(5,4),(5,1),(5,3),(4,2),(2,4),(1,2),(2,1),(5,2),(2,5),(2,3)(3,2)

Sample #2 最短路徑會經過城市1的路徑為(1,2),(2,1),(1,3),(3,1),(1,4),(4,1)

//RE:從7122開始的異世界生活
//爆肝槳吏沅的異世界狂想曲

Problem Source

Problem Set By oToToT

Subtasks

For Testdata: 0 ~ 2, Score: 20
For Testdata: 3 ~ 5, Score: 30
For Testdata: 6 ~ 8, Score: 50
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1000 65536 65536
1 1000 65536 65536
2 1000 65536 65536
3 1000 65536 65536
4 1000 65536 65536
5 1000 65536 65536
6 1000 131072 65536
7 1000 131072 65536
8 1000 131072 65536