No.1843 Tree ANDistance
レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 139
作問者 : 👑
potato167
/ テスター :
tatyam
nok0
タグ : / 解いたユーザー数 139
作問者 : 👑
potato167
/ テスター :
tatyam
nok0
問題文最終更新日: 2022-01-15 01:00:26
問題文
$N$ 頂点の木が与えられます。木の頂点にはそれぞれ $1$ から $N$ までの番号が振られています。この木の $i$ 番目の辺は頂点 $A_i$ と $B_i$ をつないでいて、辺上には正の整数 $C_i$ が置かれています。
$\sum_{u=1}^{N-1}{ \sum_{v=u+1}^{N} \text{andist}(u,v)}$
の値を求めてください。 ただし、$\text{andist}(u,v)$ は、頂点 $u$ から頂点 $v$ までの最短距離の辺上に置かれている数の $\text{AND}$ とします。 また、答えは非常に大きくなることがあるので $(10^9+7)$ で割ったあまりを出力してください。
▼$\text{AND}$ とは？
数 $x_1,x_2,...,x_n$ が与えられたときこれらの $\text{AND}$ を $A$ とすると、 $A$ は以下のように定義される。制約
- $2\leq N \leq 10^5$
- $1\leq A_{i} < B_{i}\leq N$
- $1\leq C_i \leq 10^9$
- 与えられるグラフは木である。
- 入力は全て整数
入力
$N$
$ A_1 \; B_1 \; C_1$
$ A_2 \; B_2 \; C_2$
$ \vdots $
$ A_{N-1} \; B_{N-1} \; C_{N-1}$
出力
答えを $(10^{9}+7)$ で割ったあまりを出力してください。 最後に改行してください。
サンプル
サンプル1
入力
3 1 2 5 2 3 4
出力
13
$\text{andist}(1,2)=5,\ \text{andist}(2,3)=4,\ \text{andist}(1,3)=4,\ 5+4+4=13$ より、$13$ を出力します。
サンプル2
入力
2 1 2 11111
出力
11111
サンプル3
入力
10 4 10 720486811 3 6 815722764 3 4 983953993 8 10 211236348 3 5 349109700 5 9 338069808 6 7 510511646 1 5 367286770 2 6 831398479
出力
819732336
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。