P8265 [Ynoi Easy Round 2020] TEST_63

You are given a forest consisting of rooted trees with $n$ vertices (initially there are no edges, and each vertex is the root of a rooted tree). The vertices are labeled with integers from $1$ to $n$. You need to maintain the Heavy-Light Decomposition (HLD) structure of the forest, defined as follows: For each vertex $w\;(1\le w\le n)$, let the set of its children be $\mathrm{children}(w)$. If $w$ is not a root, let its parent be $\mathrm{father}(w)$. The subtree size of a vertex $w$, denoted $\mathrm{size}(w)$, is defined as $1+\sum\limits_{u\in\mathrm{children}(w)}\mathrm{size}(u)$. If a vertex $w$ is not a leaf (i.e., $\mathrm{children}(w)\ne\varnothing$), then its heavy child $\mathrm{hc}(w)$ is defined as $\mathrm{arg}\max_{u\in\mathrm{children}(w)}size(u)\cdot n+\max(u,\mathrm{hc}(u),\mathrm{hc}(\mathrm{hc}(u)),\dots)$. That is, it is the child with the largest subtree size. If there are multiple children $u$ with the same subtree size, choose the one whose heavy chain (within the subtree rooted at $u$) contains the largest maximum vertex label. A heavy chain is a sequence of vertices $w_1,w_2,\dots,w_k\;(k>0)$ satisfying: - $w_1$ is a root, or $w_1\ne \mathrm{hc}(\mathrm{father}(w_1))$. - $w_i=\mathrm{hc}(w_{i-1})\;(2\le i\le k)$. In a tree, each vertex belongs to exactly one heavy chain. The weight of a heavy chain is $w_1\oplus w_2\oplus\dots\oplus w_k$, i.e., the bitwise XOR of the vertex labels in the sequence. You need to perform $2m$ operations in order. The operations are: - Add edge: given two vertices $a,b$, make $b$ the root of the rooted tree containing $b$ (let the sequence of vertices $t_1,t_2,\dots,t_l$ satisfy $t_l=b$, $t_1$ is the root, and $(t_i,t_{i+1}),\;1\le i

The first line contains two integers `n m`. The next $m$ lines each contain four integers `o a b k`. If $o=1$, it means first add the edge $a,b$, then query $k$. If $o=0$, it means first delete the edge $a,b$, then query $k$.

Output $m$ lines, each containing one integer, in order, which are the results of each query.

Idea: nzhtl1477, Solution: ccz181078, Code: ccz181078, Data: ccz181078. This problem uses subtask-based judging. There are $31$ test points. All test points satisfy $1\le n\le 10^5$, $1\le m\le 5\times 10^5$, $0\le o\le 1$, $1\le a\le n$, $1\le b \le n$, $1\le k\le n$, and $n,m,o,a,b,k$ are all integers. The testdata may have the following properties: - Property 1: The operations are generated randomly using the following strategy, repeated until an operation sequence of $m$ lines is generated: - Uniformly choose three integers $x,y,k$ in $[1,n]$. If $x,y$ are in different rooted trees, generate a line `1 x y k`. Otherwise, if $x$ is not a root, uniformly generate one of `0 x father(x) k` or `0 father(x) x k`. Otherwise, do nothing. - Property 2: $m=n-1$, and for $2\le i\le n$, the $i$-th line of the testdata is `1 a i k`, where $a$ is chosen uniformly from the integers in $[1,i-1]$. - Property 3: $m=n-1$, and for $2\le i\le n$, the $i$-th line of the testdata is `1 i b k`, where $b$ is chosen uniformly from the integers in $[1,i-1]$. - Other constraints on $n,m$. The properties of each test point are: Test point 1: $n=10,\;m=50$, satisfies Property 1, 10 points. Test point 2: $n=100,\;m=500$, satisfies Property 1, 10 points. Test point 3: $n=1000,\;m=5000$, satisfies Property 1, 10 points. Test point 4: satisfies Property 2, 15 points. Test point 5: satisfies Property 3, 15 points. Test points 6 to 10: satisfy Property 1, 20 points. Test points 11 to 31: no special constraints, 20 points. Translated by ChatGPT 5