P3233 [HNOI2014] World Tree

The World Tree is an unimaginably huge tree whose sprawling branches form the entire world. Here live various races and beings. They all worship the goddess Alison, who stands for absolute justice and fairness. In their creed, fairness is the fundamental cornerstone that allows the World Tree to thrive and keep running. The shape of the World Tree can be modeled mathematically: there are $n$ races in the World Tree, numbered from $1$ to $n$, each living in a settlement also numbered from $1$ to $n$, and a race’s number equals its settlement’s number. Some settlements are connected by bidirectional roads, each of length $1$. It is guaranteed that the connections form a tree, that is, every settlement is reachable from every other, and there are no cycles. The distance between two settlements is defined as the length of the unique path connecting them. For example, if there is a road between settlements $a$ and $b$, and a road between $b$ and $c$, then since each road has length $1$ and cycles are impossible, the distance between $a$ and $c$ is $2$. For fairness, in year $i$, the king of the World Tree authorizes $m_i$ settlements as temporary offices. For a race $x$ (where $x$ is the race’s number), if the nearest temporary office to race $x$ is at settlement $y$ (where $y$ is the settlement number of the office), then race $x$ accepts the administration of the office at $y$ (if multiple temporary offices are at the same minimum distance to that settlement, then $y$ is the office with the smallest number among them). Now the king wants to know, over $q$ years, after the authorizations in each year are completed, how many races each temporary office will administer that year (the settlement where an office is located also accepts that office’s administration). This task is handed to you, the wise primate: the programmer. Please help the king complete this task.

The first line contains a positive integer $n$, the number of races in the World Tree. The next $n-1$ lines each contain two positive integers $x, y$, indicating that there is a bidirectional road of length $1$ between settlements $x$ and $y$. The next line contains a positive integer $q$, the number of years the king queries. Then follow $q$ blocks, each consisting of two lines: in the $i$-th block, the first line contains one positive integer $m_i$, the number of temporary offices authorized in year $i$. The second line contains $m_i$ positive integers $h_1, h_2, \ldots, h_{m_i}$, the settlement numbers authorized as temporary offices (guaranteed to be all distinct).

Output $q$ lines. In the $i$-th line, output $m_i$ integers, where the $j$-th number ($j = 1, 2, \ldots, m_i$) is the number of races administered by the temporary office at settlement $h_j$ authorized in year $i$.

For $100\%$ of the testdata, $N\leq 300000$, $q\leq 300000$, $\sum^q_{i=1}m_i \leq 300000$. Translated by ChatGPT 5