P16529 [THUPC 2026 Final] Phantom Light Afterimage

From the finals of the 2026 Tsinghua University Programming Contest and Collegiate Invitational (THUPC2026). Resources such as editorials can be found at https://github.com/dapingguo8/THUPC2026-final. > To leave everyone a unique 10th anniversary memory, Xiao T and Xiao S set up a large interactive art installation called "Phantom Light Afterimage" in the main venue. > > The installation consists of many floating image nodes, connected by light beams into the shape of a tree, and each node is equipped with a light-and-shadow filter of a different color. You arrived at the console and found that you can interact freely: whenever you adjust parameters on the console, the system temporarily activates only the light beams within a specific index interval, causing the whole afterimage network to split in midair into several independent connected regions. Filters of the same color within the same connected region will produce optical interference: when this color appears an even number of times in the connected component, it becomes invisible; when it appears an odd number of times, its display effect is the same as a single filter of that color. > > The visual effect of breaking and recombining light and shadow is fascinating. You became very interested in the hidden structural changes: under each such partial activation, for every isolated connected region, how many different colors of visible filters does it contain?

The "Phantom Light Afterimage" installation can be abstracted as a tree with $n$ nodes. Each node represents an image node, and the filter color of node $i \ (1 \le i \le n)$ is $c_i$. There are $n - 1$ light beams connecting nodes, and they are numbered from $1$ to $n - 1$ in installation order. During your exploration, you recorded testdata from $m$ dynamic effect tests. In each test, you specify a light-beam index interval $[l, r]$. Suppose that only the light beams whose indices fall within this interval are kept, and all light beams whose indices are not in $[l, r]$ are disconnected. Then the originally connected network will split into several independent connected components. To further analyze the structural changes, for each test you need to compute: the sum, over all resulting connected components, of the number of distinct visible filter colors contained in that component.

The first line contains two positive integers $n, m \ (1 \le n \le 10 ^ 5, \ 1 \le m \le 3\times10 ^ 5)$, representing the number of image nodes and the number of tests. The second line contains $n$ positive integers $c_1, c_2, \dots, c_n \ (1 \le c_i \le n)$, representing the filter color of each image node. The next $n - 1$ lines describe the light beams. The $i \ (1 \le i \le n - 1)$-th of these lines contains two positive integers $u_i, v_i \ (1 \le u_i, v_i \le n)$, indicating that light beam number $i$ connects these two nodes. The next $m$ lines each contain two positive integers $l, r \ (1 \le l \le r \le n - 1)$, representing the light-beam index interval of one test.

Output $m$ lines. Each line contains one positive integer, in order, representing for each test the sum of the numbers of distinct visible filter colors in all resulting connected components.

Translated by ChatGPT 5