以下页面来自赛事官方发布的原题PDF,已完整保存并渲染到本地。


可复制的 PDF 提取文本
Problem K
Tree Quiz
Time limit: 4 seconds
Your friend wants to quiz you. You are given a rooted tree with n nodes, numbered from 1 to n. For every node i, its
parent is node pi, except for the root (the node without a parent) which has pi = 0. Node u is an ancestor of node v if
either u = v, or node u is an ancestor of the parent of node v (if it exists).
We say that node z is a common ancestor of nodes x and y if node z is an ancestor of both nodes x and y. We say
that node z is the lowest common ancestor of nodes x and y if it is a common ancestor of nodes x and y, and every
common ancestor of nodes x and y is also an ancestor of node z. We denote the lowest common ancestor of nodes x
and y by LCA(x, y). In particular, LCA(x, x) = x.
Your friend would like to run the following pseudocode:
let L be an empty array
for x = 1 to n
for y = 1 to n
append ((x - 1) * n * n + (LCA(x, y) - 1) * n + (y - 1)) to L
sort L in non-decreasing order
Your friend has q questions, numbered from 1 to q. In question j, you are given an integer kj and asked to find the
kj-th element of the array L. Note that L is 1-indexed, so the indices range from 1 to n2, inclusive. To pass the quiz,
you have to answer all of the questions.
Input
The first line of input contains two integers n and q (1 ≤n ≤100 000; 1 ≤q ≤100 000). The second line contains n
integers p1, p2, . . . , pn (0 ≤pi ≤n for all i). It is guaranteed that the given values represent a rooted tree. Each of the
next q lines contains an integer. The j-th line contains kj (1 ≤kj ≤n2).
Output
For each question in order, output an integer representing the answer to the question.
Sample Input #1 Sample Output #1
5 3 0
3 0 2 2 3 82
1 124
18
25
Explanation for the sample input/output #1
The tree in the input is illustrated by Figure K.1.
ICPC Asia Pacific Championship 2024 Problem K: Tree Quiz
2
3 4
1 5
Figure K.1: Illustration of the tree in sample input #1.
The elements of L are
(0, 6, 8, 12, 14, 30, 31, 32, 33, 34, 56, 58, 60, 62, 64, 80, 81, 82, 84, 93, 106, 108, 110, 112, 124).
ICPC Asia Pacific Championship 2024 Problem K: Tree Quiz