問題一覧 > 通常問題

No.1843 Tree ANDistance

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 134
作問者 : 👑 potato167potato167 / テスター : nok0nok0 👑 tatyamtatyam
5 ProblemId : 7453 / 出題時の順位表 / 自分の提出
問題文最終更新日: 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$ は以下のように定義される。
  • $A$ を二進数表記したときの $2^k\,(0\leq k)$ の位は、$x_1,x_2,\dots,x_n$ のすべての数の $2^k$ の位が $1$ なら $1$ 、そうでないなら $0$ とする。
  • 例えば、$3$ と $6$ が与えられたとき、これらの $\text{AND}$ は $2$ となる。

    制約

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