問題一覧 > 通常問題

No.1843 Tree ANDistance

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 140
作問者 : 👑 potato167 / テスター : tatyam nok0
6 ProblemId : 7453 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-01-15 01:00:26

問題文

N 頂点の木が与えられます。木の頂点にはそれぞれ 1 から N までの番号が振られています。この木の i 番目の辺は頂点 Ai と Bi をつないでいて、辺上には正の整数 Ci が置かれています。

∑u=1N−1∑v=u+1Nandist(u,v)

の値を求めてください。 ただし、andist(u,v) は、頂点 u から頂点 v までの最短距離の辺上に置かれている数の AND とします。 また、答えは非常に大きくなることがあるので (109+7) で割ったあまりを出力してください。

▼AND とは？ 数 x1,x2,...,xn が与えられたときこれらの AND を A とすると、 A は以下のように定義される。
  • A を二進数表記したときの 2k(0≤k) の位は、x1,x2,…,xn のすべての数の 2k の位が 1 なら 1 、そうでないなら 0 とする。
    • 例えば、3 と 6 が与えられたとき、これらの AND は 2 となる。

    制約

    • 2≤N≤105
    • 1≤Ai<Bi≤N
    • 1≤Ci≤109
    • 与えられるグラフは木である。
    • 入力は全て整数

    入力

    N
A1B1C1
A2B2C2
⋮
AN−1BN−1CN−1

    出力

    答えを (109+7) で割ったあまりを出力してください。 最後に改行してください。

    サンプル

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

    andist(1,2)=5, andist(2,3)=4, 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もしくは右上の雲マークをクリックしてアカウントを作成してください。