DMOPC '15 Contest 7 P5 - Ariadne's Thread

View as PDF

Submit solution

Points: 17 (partial)
Time limit: 1.0s
Memory limit: 256M

Problem types

The Labyrinth was said to be an ever-shifting, inescapable maze — Daedalus's most cunning creation. Those who were unfortunate enough to find themselves in it were destined to be trapped for the rest of their lives — which were usually quite short. Our hero Theseus was sent on a seemingly impossible quest to slay the Minotaur, a monster that lurked in the depths of the Labyrinth. Fortunately, his beloved, Ariadne, was just as smart as Daedalus.

Ariadne had managed to sneak a peek at the blueprints for the Labyrinth and noticed that it was actually in the form of a rooted tree consisting of N nodes, numbered 1 through N. To prevent the rather dim Theseus from getting himself lost, she gave him a ball of thread as well as specific instructions on how to explore the maze.

Let the current node that Theseus is at be u. Then:

  • Theseus should move to the leftmost unvisited child of u
  • If all of u's children have been visited or if u is a leaf, Theseus should backtrack and return to u's parent

But Ariadne is still anxious. So she decided to ask you, her trusty adviser, Q queries of the following form:

Suppose that Theseus enters the Labyrinth at node u and the Minotaur is located at node v, how many edges will Theseus pass before reaching the Minotaur if he follows Ariadne's instructions perfectly?


Subtask 1 [10%]

2 \le N \le 100, 1 \le Q \le 100

Subtask 2 [20%]

2 \le N \le 5\,000, 1 \le Q \le 100\,000

Subtask 3 [70%]

2 \le N \le 100\,000, 1 \le Q \le 100\,000

It is guaranteed that node 1 will always be the root of the tree.

Input Specification

The first line of input will contain N, the number of nodes in the tree.

The following N lines will describe the tree. The i^{th} of these lines begin with an integer C_i, denoting the number of children of node i, followed by C_i space-separated integers, the labels of its children from left to right.

The next line will contain Q, the number of queries.

The following Q lines will each contain a query in the form u v.

Output Specification

Output the answer to each query on a separate line.

Sample Input

2 2 3
3 4 5 8
2 6 7
1 9
1 10
9 8
5 1
1 2

Sample Output


Explanation for Sample Output

The Labyrinth looks like this:

In the first query, Theseus will walk the following path: 9 \rightarrow 4 \rightarrow 2 \rightarrow 5 \rightarrow 2 \rightarrow 8.

In the second query: 5 \rightarrow 2 \rightarrow 4 \rightarrow 9 \rightarrow 4 \rightarrow 2 \rightarrow 8 \rightarrow 2 \rightarrow 1.

In the third query: 1 \rightarrow 2.


  • 0
    JY900  commented on Jan. 15, 2021, 2:25 a.m.

    HLD is too op 😫