問題一覧 > 通常問題

No.1103 Directed Length Sum

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 161
作問者 : Ldio03Ldio03 / テスター : jupirojupiro
7 ProblemId : 4203 / 出題時の順位表
問題文最終更新日: 2020-07-03 23:46:41

問題文

$N$ 頂点の有向木があり、$i$ 番目の辺は頂点 $A_i$ から頂点 $B_i$ に向かって伸びています。また、根以外の各頂点には、その親から一本の有向辺が伸びています。
関数$f(a,b)$を次のように定義します。
$f(a,b)=$頂点 $a$ から頂点 $b$ へ行くパスの長さ(頂点 $a$ から頂点 $b$ に行くときに経由する辺の数)
ただし、パスが存在しなければ$f(a,b)=0$ とします。また、$f(a,a)=0$ とします。
このとき、$\displaystyle \sum_{i=1}^n \sum_{j=1}^n f(i,j)$を求めてください。答えは大きくなることがあるので、$10^9+7 $ で割った余りを求めてください。

補足

PyPy3で通ることを確認していますが、Pythonでは確認できていません。

入力

$N$
$A_1\ B_1$
$A_2\ B_2$
:
$A_{N-1}\ B_{N-1}$

制約は以下の通りです。
・$3 \le N \le 10^6$
・$i \neq j $であれば$(A_i,B_i) \neq (A_j,B_j)$
・$1 \le A_i,B_i \le N (1 \le i \le N - 1)$
・与えられるグラフは有向木である

出力

答えを出力してください。 最後に改行してください。

サンプル

サンプル1
入力
3
1 2
1 3
出力
2

求めるべき値は$f(1,2)+f(1,3)+f(2,1)+f(2,3)+f(3,1)+f(3,2)$であり、頂点$1$から頂点$2,3$には長さ$1$のパスが存在するので$f(1,2)=f(1,3)=1$です。一方、例えば頂点$2$から頂点$3$に行くパスは存在しないので$f(2,3)=0$です。

サンプル2
入力
5
2 1
1 3
1 4
3 5
出力
13

例えば、$f(3,4)=0,f(2,5)=3$です。なお、根は頂点$1$とは限りません。$($このケースの場合$2)$

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。