Subtree Minimum Query
You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.
Description
You are given a rooted tree consisting of n vertices. Each vertex has a number written on it; number ai is written on vertex i.
Let's denote d(i, j) as the distance between vertices i and j in the tree (that is, the number of edges in the shortest path from i to j). Also let's denote the k-blocked subtree of vertex x as the set of vertices y such that both these conditions are met:
- x is an ancestor of y (every vertex is an ancestor of itself);
- d(x, y) ≤ k.
You are given m queries to the tree. i-th query is represented by two numbers xi and ki, and the answer to this query is the minimum value of aj among such vertices j such that j belongs to ki-blocked subtree of xi.
Write a program that would process these queries quickly!
Note that the queries are given in a modified way.
The first line contains two integers n and r (1 ≤ r ≤ n ≤ 100000) — the number of vertices in the tree and the index of the root, respectively.
The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 109) — the numbers written on the vertices.
Then n - 1 lines follow, each containing two integers x and y (1 ≤ x, y ≤ n) and representing an edge between vertices x and y. It is guaranteed that these edges form a tree.
Next line contains one integer m (1 ≤ m ≤ 106) — the number of queries to process.
Then m lines follow, i-th line containing two numbers pi and qi, which can be used to restore i-th query (1 ≤ pi, qi ≤ n).
i-th query can be restored as follows:
Let last be the answer for previous query (or 0 if i = 1). Then xi = ((pi + last) mod n) + 1, and ki = (qi + last) mod n.
Print m integers. i-th of them has to be equal to the answer to i-th query.
Input
The first line contains two integers n and r (1 ≤ r ≤ n ≤ 100000) — the number of vertices in the tree and the index of the root, respectively.
The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 109) — the numbers written on the vertices.
Then n - 1 lines follow, each containing two integers x and y (1 ≤ x, y ≤ n) and representing an edge between vertices x and y. It is guaranteed that these edges form a tree.
Next line contains one integer m (1 ≤ m ≤ 106) — the number of queries to process.
Then m lines follow, i-th line containing two numbers pi and qi, which can be used to restore i-th query (1 ≤ pi, qi ≤ n).
i-th query can be restored as follows:
Let last be the answer for previous query (or 0 if i = 1). Then xi = ((pi + last) mod n) + 1, and ki = (qi + last) mod n.
Output
Print m integers. i-th of them has to be equal to the answer to i-th query.
5 2
1 3 2 3 5
2 3
5 1
3 4
4 1
2
1 2
2 3
2
5
20231121集训
- Status
- Done
- Rule
- IOI
- Problem
- 6
- Start at
- 2023-11-21 19:00
- End at
- 2023-11-21 21:00
- Duration
- 2 hour(s)
- Host
-
SamuelXuch
- Partic.
- 15