No.1103 Directed Length Sum
タグ : / 解いたユーザー数 208
作問者 :
Ldio03
/ テスター :
jupiro
問題文
$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もしくは右上の雲マークをクリックしてアカウントを作成してください。