P7973 [KSN2021] Binary Land

You are given a graph with $N$ vertices. Each vertex has a weight $A_i$ and a value $B_i$. There is an undirected edge between two vertices $x, y$ if and only if $A_x\text{ xor }A_y>\max(A_x,A_y)$. You need to compute, for $i=1,2,\cdots n$ in order, the sum of values of all vertices in the connected component that contains vertex $i$.

The first line contains a positive integer $N$. The second line contains $N$ positive integers $A_i$. The third line contains $N$ positive integers $B_i$.

Output $N$ lines. The $i$-th line contains an integer representing the sum of values of all vertices in the connected component that contains vertex $i$.

**Constraints** **This problem uses bundled testdata.** - Subtask 1 (8 points): There is only one test case, with $N=8$, $A=[6,39,11,63,3,39,1,43]$, $B=[4,8,3,7,9,1,2,2]$. - Subtask 2 (13 points): Guaranteed $N \leq 200$. - Subtask 3 (10 points): Guaranteed $N \leq 2000$. - Subtask 4 (4 points): Guaranteed $A_1=A_2=\cdots=A_n$. - Subtask 5 (7 points): Guaranteed that there exists a non-negative integer $k$ such that $A_i=2^k$. - Subtask 6 (19 points): $A_i\leq 2^{12}-1$. - Subtask 7 (39 points): No special restrictions. For all testdata, $1 \leq N \leq 10^5$, $1 \leq A_i \leq 2^{30}-1$, $1 \leq B_i \leq 10^9$. Translated by ChatGPT 5