問題一覧 > 通常問題

No.1103 Directed Length Sum

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

問題文

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

補足

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

入力

N
A1 B1
A2 B2
:
AN1 BN1

制約は以下の通りです。
3N106
ijであれば(Ai,Bi)(Aj,Bj)
1Ai,BiN(1iN1)
・与えられるグラフは有向木である

出力

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

サンプル

サンプル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もしくは右上の雲マークをクリックしてアカウントを作成してください。