問題一覧 > 通常問題

No.2377 SUM AND XOR on Tree

レベル : / AI推定難易度 : 1400 / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 66
作問者 : poyon / テスター : KowerKoint2010 timi hibit_at 👑 seekworser
お気に入りにしたユーザー ProblemId : 9676 / 自分の提出
問題文最終更新日: 2023-07-06 20:18:56
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 396 (Asakatsu Presents 2) (順位表) の他の問題:

Problem Statement

There is a tree $T$ with $N$ vertices, numbered from $1$ to $N$.
The $i$-th edge connects vertices $u_i$ and $v_i$. A non-negative integer $A_i$ is written on vertex $i$.

There are $2^{N-1}$ graphs $G$ obtainable by deleting $0$ or more edges from the tree $T$.
For each graph $G$, compute the value of $f(G)$, and find the sum of these values modulo $998244353$.

Here, $f(G)$ is the value obtained by taking the $\mathrm{XOR}$ of $A_i$ for each connected component of the graph $G$, and then taking the $\mathrm{AND}$ of those values.
More precisely, it is defined as follows.

  • $f(G) = g(C_1) \ \mathrm{AND} \ \cdots \ \mathrm{AND} \ g(C_{m_G})$
    • $g(C_j) = A_{k_{j,1}} \ \mathrm{XOR} \ \cdots \ \mathrm{XOR} \ A_{k_{j,n_j}} \ (1 \leq j \leq m_G)$
    • The graph $G$ has $m_G$ connected components, denoted by $C_1, \dots , C_{m_G}$
    • The connected component $C_j$ has $n_j$ vertices, denoted by $k_{j,1}, \dots , k_{j,n_j}$

Note that $\mathrm{AND}$ denotes the bitwise $\mathrm{AND}$ operation, and $\mathrm{XOR}$ denotes the bitwise $\mathrm{XOR}$ operation.

Input

$N$
$u_1 \ v_1$
$u_2 \ v_2$
$\vdots$
$u_{N-1} \ v_{N-1}$
$A_1 \ A_2 \ \dots \ A_N$
  • $2 \leq N \leq 10^5$
  • $0 \leq A_i < 2^{30}$
  • $1 \leq u_i, v_i \leq N$
  • The given graph is a tree.
  • All input values are integers.

Output

Output the answer.

Sample

Sample 1
Input
3
1 2
1 3
1 2 3
Output
5

There are $4$ ways to delete edges.

  • When deleting $0$ edges, $f(G) = A_1 \ \mathrm{XOR} \ A_2 \ \mathrm{XOR} \ A_3 = 0$
  • When deleting the $1$-st edge, $f(G) = (A_1 \ \mathrm{XOR} \ A_3) \ \mathrm{AND} \ A_2 = 2$
  • When deleting the $2$-nd edge, $f(G) = (A_1 \ \mathrm{XOR} \ A_2) \ \mathrm{AND} \ A_3 = 3$
  • When deleting the $1$-st and $2$-nd edges, $f(G) = A_1 \ \mathrm{AND} \ A_2 \ \mathrm{AND} \ A_3 = 0$

Therefore, the sum is $0 + 2 + 3 + 0 = 5$.

Sample 2
Input
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
Output
159370513

Note that the sum must be computed modulo $998244353$.

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