TopCoder

Thumb hsnu2016
Adrien Wu
$ \begin{align} AC \times 2^9 \\ \text{New TIOJ ?} \end{align} $

User's AC Ratio

77.8% (7/9)

Submission's AC Ratio

27.1% (23/85)

Tags

NOI

Description

「被洗腦?」小向略感驚訝。畢竟…誰會沒事洗腦一個茶葉……
「你臉上的表情感覺像是在瞧不起人噢=ㄦ=」
「有嗎…」
「我本來真的是條龍,只是被洗腦又被變成這種丑角樣,我也很無奈啊…」
「啊…這樣啊…真是抱歉了…」
「先不說這個了。看來我們兩個短期內的目標都一樣呢。」
「是啊,我們得快點趕去森林中心。我得解救希爾伯特,而你還得解除你被下的詛咒。事不宜遲,我們快瞬間移動過去吧。」
「等等!」烏龍突然大喊。「這附近都被結界圍住了。在這裡瞬間移動系的魔法是無法生效的。」
「況且,」烏龍緊接著說,「以你的程度…恐怕…」
其實小向自己也知道的,自己多麼的無力。儘管如此,她也想,就這一次,幫助到其它人。然而烏龍的一句話重重地打擊了小向,彷彿將緊握著最後一絲希望之人的手硬是扳開了。
「不過沒關係,我有方法:短期提升魔力的方法。」
烏龍接著開始解釋:
「其實在其它平行世界中,有個你的魔力非常的高。而我接下來要做的就是將那個平行世界的你的魔力共享給你。然而共享當然不是說做就做,而是取決於兩個平行世界的距離。
具體地說,現在和我們這個世界相通的平行世界共有$N$個(含目前所在的世界),而有$N-1$條魔力隧道(每個隧道連接兩個平行世界)將$N$個平行世界連起來,使得任兩個平行世界都可藉由一系列的魔力隧道相通。而將某個平行世界的魔力共享給你的難度就是接通這個世界與那個平行世界的魔力隧道個數…」

講到這裡,烏龍停了一下確定小向的腦袋沒有混亂。令人意外地,小向的眼神不像是混亂中的樣子。烏龍便放心地繼續:
「不過,我可以讓一些魔力隧道縮短,使得他對共享難度的貢獻由1變為0。也就是說,將某個平行世界的魔力共享給你的難度變為兩個世界之間的路徑上,沒被我縮短的魔力隧道的個數。當然,這樣的魔法還是有限制的。對於任何一個平行世界,連接它的魔力隧道最多只能有兩條被我縮短。」
「所以要找最好的縮短方法……」
「是的。不過最麻煩的是,我雖然能繪出平行世界之間的關係圖以及標示出我們的所在位置,但我無法知道事先知道哪個平行世界的你魔力最高:我必須先縮短魔力隧道後才能探知其它世界的你的魔力。」
「所以要使最大共享難度最小吧!可是為什麼你要告訴我這些?」
「因為我不知道怎麼縮比較好啊。」烏龍搔搔頭,「感覺上你的頭腦比我還要靈光呢。」
「太好了!終於有我可以做的事了!」小向心想,「絕對不能放過這次大展身手的機會。」

Input Format

第一行有一個正整數$N\leq 5\times 10^ 5$,代表平行世界個數。
接下來的$N-1$行,每行有兩個整數$0\leq a,b< N$,代表編號a和編號b之間連有一條魔力隧道。其中目前的世界是編號0。

子任務(測資) 額外限制 分數
1 (0~4) $N\leq 20$ 12
2 (5~9) $N\leq 200$ 16
3 (10~14) $N\leq 10^ 4$ 20
4 (15~19) $N\leq 10^ 5$ 24
5 (20~24) 28

Output Format

輸出一行,包含兩個數,分別代表最大共享難度的最小值以及最佳方案個數。由於最佳方案個數可能很大,請將答案模1,000,000,007後輸出。

Sample Input

5
0 1
0 2
0 3
1 4

Sample Output

1 10

Hints

……
儀式結束了,而小向也獲得了來自其它平行世界的小向的魔力了。
「太好了,來試個幾招吧。」
「別急,現在你一定還不習慣強大的魔力的,亂來會出事的。」烏龍急忙阻止。
「先練習如何控制這股強大的魔力吧。」

Problem Source

Problem Set / Description by Paupière
題目改編自NOI

Subtasks

No. Testdata Range Score
1 0~4 12
2 5~9 16
3 10~14 20
4 15~19 24
5 20~24 28

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 2000 131072 262144 1
1 2000 131072 262144 1
2 2000 131072 262144 1
3 2000 131072 262144 1
4 2000 131072 262144 1
5 2000 131072 262144 2
6 2000 131072 262144 2
7 2000 131072 262144 2
8 2000 131072 262144 2
9 2000 131072 262144 2
10 2000 131072 262144 3
11 2000 131072 262144 3
12 2000 131072 262144 3
13 2000 131072 262144 3
14 2000 131072 262144 3
15 2000 131072 262144 4
16 2000 131072 262144 4
17 2000 131072 262144 4
18 2000 131072 262144 4
19 2000 131072 262144 4
20 2000 131072 262144 5
21 2000 131072 262144 5
22 2000 131072 262144 5
23 2000 131072 262144 5
24 2000 131072 262144 5