World tree - MarisaOJ: Marisa Online Judge

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