問題一覧 > 通常問題

No.2377 SUM AND XOR on Tree

レベル : / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 60
作問者 : poyonpoyon / テスター : KowerKoint2010KowerKoint2010 timitimi hibit_athibit_at 👑 seekworserseekworser
1 ProblemId : 9676 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-07-06 20:18:56

問題文

NN 頂点の木 TT があり、各頂点には 11 から NN までの番号が振られています。
ii 番目の辺は頂点 uiu_i と頂点 viv_i を結んでいます。頂点 ii には非負整数 AiA_i が書かれています。

TT から 00 本以上の辺を削除して得られるグラフ GG2N12^{N-1} 通りありますが、
それぞれのグラフ GG について f(G)f(G) の値を求めて、その総和を 998244353998244353 で割った余りを求めてください。

ここで、f(G)f(G) とは、グラフ GG の連結成分ごとに AiA_iXOR\mathrm{XOR} を取り、それらの値の AND\mathrm{AND} を取った値です。
より厳密には以下の通りです。

  • f(G)=g(C1) AND  AND g(CmG)f(G) = g(C_1) \ \mathrm{AND} \ \cdots \ \mathrm{AND} \ g(C_{m_G})
    • g(Cj)=Akj,1 XOR  XOR Akj,nj (1jmG)g(C_j) = A_{k_{j,1}} \ \mathrm{XOR} \ \cdots \ \mathrm{XOR} \ A_{k_{j,n_j}} \ (1 \leq j \leq m_G)
    • グラフ GG の連結成分は mGm_G 個あり、C1,,CmGC_1, \dots , C_{m_G} で表される
    • 連結成分 CjC_j の頂点は njn_j 個あり、kj,1,,kj,njk_{j,1}, \dots , k_{j,n_j}で表される

なお、AND\mathrm{AND} はビット単位 AND\mathrm{AND} 演算、XOR\mathrm{XOR} はビット単位 XOR\mathrm{XOR} 演算を表します。

入力

NN
u1 v1u_1 \ v_1
u2 v2u_2 \ v_2
\vdots
uN1 vN1u_{N-1} \ v_{N-1}
A1 A2  ANA_1 \ A_2 \ \dots \ A_N
  • 2N1052 \leq N \leq 10^5
  • 0Ai<2300 \leq A_i < 2^{30}
  • 1ui,viN1 \leq u_i, v_i \leq N
  • 与えられるグラフは木
  • 入力はすべて整数

出力

答えを出力してください。

サンプル

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

辺を削除する方法は 44 通りあります。

  • 00 本の辺を削除する場合、f(G)=A1 XOR A2 XOR A3=0f(G) = A_1 \ \mathrm{XOR} \ A_2 \ \mathrm{XOR} \ A_3 = 0
  • 11 番目の辺を削除する場合、f(G)=(A1 XOR A3) AND A2=2f(G) = (A_1 \ \mathrm{XOR} \ A_3) \ \mathrm{AND} \ A_2 = 2
  • 22 番目の辺を削除する場合、f(G)=(A1 XOR A2) AND A3=3f(G) = (A_1 \ \mathrm{XOR} \ A_2) \ \mathrm{AND} \ A_3 = 3
  • 11 番目の辺と 22 番目の辺を削除する場合、f(G)=A1 AND A2 AND A3=0f(G) = A_1 \ \mathrm{AND} \ A_2 \ \mathrm{AND} \ A_3 = 0

よって、総和は 0+2+3+0=50 + 2 + 3 + 0 = 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

総和を 998244353998244353 で割った余りで求めることに注意してください。

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