World tree - MarisaOJ: Marisa Online Judge

World tree

Time limit: 1500 ms
Memory limit: 128 MB
Given a tree graph with $N$ vertices and $Q$ queries. The $i$-th query consists of $m_i$ special vertices $x_1,x_2,x_3,\dots x_{m_i}$. A vertex $u$ on the tree is considered to be occupied by a special vertex $x$ if the distance from $u$ to $x$ is the smallest among the $m_i$ special vertices (if the distance from $u$ to $x_1$ is equal to the distance from $u$ to $x_2$ and $x_1 < x_2$, then $u$ will preferentially be occupied by $x_1$). For each query, print the number of vertices that each special vertex $x_i$ occupies. ### Input - The first line contains an integer $N$. - The next $N-1$ lines describe the edges of the tree. - The following line contains an integer $Q$. - The next $Q \times 2$ lines are structured as follows: - The first line contains an integer $m_i$. - The next line contains $m_i$ integers $x_1, x_2, \ldots$, which are the special vertices. ### Output - Output the answer for each query in the order of the input. ### Constraints - $N, Q \le 500000$. - $m_i, x_i \le n$. - $\sum_{i=1}^{Q} m_i$ $\le 500000$ ### Example Input: ``` 10 2 1 3 2 4 3 5 4 6 1 7 3 8 3 9 4 10 1 1 4 8 7 10 3 ``` Output: ``` 1 1 3 5 ```
Topic
Tree
Dynamic Programming
Rating 2000
Source HNOI
Solution (0) Solution