No.2377 SUM AND XOR on Tree
レベル : / 実行時間制限 : 1ケース 4.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 60
作問者 :
poyon
/ テスター :
KowerKoint2010
timi
hibit_at
👑
seekworser
タグ : / 解いたユーザー数 60
作問者 :




問題文最終更新日: 2023-07-06 20:18:56
問題文
頂点の木 があり、各頂点には から までの番号が振られています。
番目の辺は頂点 と頂点 を結んでいます。頂点 には非負整数 が書かれています。
木 から 本以上の辺を削除して得られるグラフ は 通りありますが、
それぞれのグラフ について の値を求めて、その総和を で割った余りを求めてください。
ここで、 とは、グラフ の連結成分ごとに の を取り、それらの値の を取った値です。
より厳密には以下の通りです。
- グラフ の連結成分は 個あり、 で表される
- 連結成分 の頂点は 個あり、で表される
なお、 はビット単位 演算、 はビット単位 演算を表します。
入力
- 与えられるグラフは木
- 入力はすべて整数
出力
答えを出力してください。
サンプル
サンプル1
入力
3 1 2 1 3 1 2 3
出力
5
辺を削除する方法は 通りあります。
- 本の辺を削除する場合、
- 番目の辺を削除する場合、
- 番目の辺を削除する場合、
- 番目の辺と 番目の辺を削除する場合、
よって、総和は となります。
サンプル2
入力
12 1 2 1 7 2 3 2 4 2 6 3 11 4 5 4 8 5 10 8 9 8 12 353757523 442052636 38474683 454295822 886828797 329385635 709686492 100655361 541398767 782865336 996474425 506498311
出力
159370513
総和を で割った余りで求めることに注意してください。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。