問題一覧 > 通常問題

No.1333 Squared Sum

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 47
作問者 : penguinmanpenguinman / テスター : tpynerivertpyneriver
3 ProblemId : 5436 / 出題時の順位表
問題文最終更新日: 2021-01-17 04:34:23

問題文

$N$ 頂点の木が与えられます。$i$ 番目の辺は頂点 $u_i$ と $v_i$ を双方向に結び、その長さは $w_i$ です。

$d(x,y)$ を頂点 $x$ と $y$ の最短距離とします。

$\displaystyle \sum_{i=1}^{N-1} \sum_{j=i+1}^{N}d(i,j)^2$ を求めてください。

これは非常に大きくなることがあるので、$10^9+7$ で割った余りを出力してください。

入力

$N$
$u_1\ v_1\ w_1$
$u_2\ v_2\ w_2$
$︙$
$u_{N-1}\ v_{N-1}\ w_{N-1}$
  • $1≤N≤2×10^5$
  • $1≤u_i,\ v_i≤N$
  • $u_i≠v_i$
  • $1≤w_i≤10^9$
  • 与えられるグラフは木
  • 入力は全て整数

出力

$\displaystyle \sum_{i=1}^{N-1} \sum_{j=i+1}^{N}d(i,j)^2$ を $10^9+7$ で割った余りを出力してください。

最後に改行してください。

サンプル

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

$1^2+2^2+3^2=14$ です。

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

サンプル3
入力
6
3 5 192329
4 6 293129
6 2 129532
1 2 39237
6 3 57325762
出力
219459352

$10^9+7$ で割った余りを出力してください。

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