No.2377 SUM AND XOR on Tree
タグ : / 解いたユーザー数 66
作問者 :
poyon
/ テスター :
KowerKoint2010
timi
hibit_at
👑 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もしくは右上の雲マークをクリックしてアカウントを作成してください。