atcoder#MUJINPC2017D. Oriented Tree
Oriented Tree
题目描述
頂点の木 があります。 頂点には から までの番号が振られています。 各 について、 番目の辺は頂点 と頂点 を繋いでいます。
すぬけ君は、 のすべての辺をそれぞれ好きな向きに向き付け、有向グラフ を作ろうとしています。 ( は 通りありえます。)
をひとつ固定したとき、各 について を次のように定義します。
- (頂点 から頂点 までのパスに沿って 上を移動するとき、辺の向きと逆向きに通るような辺の本数)
特に、各 について です。 また、一般に であることに注意してください。
さらに、 を次のように定義します。
すぬけ君は、 が最小値をとるように を作ろうとしています。 が最小値をとるような は何通りありうるでしょうか? で割った余りを求めてください。
输入格式
入力は以下の形式で標準入力から与えられる。
输出格式
が最小値をとるような は何通りありうるか? で割った余りを出力せよ。
4
1 2
1 3
1 4
2
4
1 2
2 3
3 4
6
6
1 2
1 3
1 4
2 5
2 6
14
10
2 4
2 5
8 3
10 7
1 6
2 8
9 5
8 6
10 6
102
提示
制約
- 入力のグラフは木である。
Sample Explanation 1
の最小値は です。 が最小値をとるような は、次図の 通りです。 ![](https://atcoder.jp/img/mujin/de49901ddf69d8565fde5b6870afb595.png)
Sample Explanation 2
の最小値は です。 が最小値をとるような は、次図の 通りです。 ![](https://atcoder.jp/img/mujin/dcb377e8c7fe15d6dd0cb815dc57c41a.png)