題目連結：http://codeforces.com/contest/1006/problem/E
題面：
In this problem you will have to help Berland army with organizing their command delivery system.
There are nn officers in Berland army. The first officer is the commander of the army, and he does not have any superiors. Every other officer has exactly one direct superior. If officer aa is the direct superior of officer bb, then we also can say that officer bb is a direct subordinate of officer aa.
Officer xx is considered to be a subordinate (direct or indirect) of officer yy if one of the following conditions holds:
- officer yy is the direct superior of officer xx;
- the direct superior of officer xx is a subordinate of officer yy.
For example, on the picture below the subordinates of the officer 33 are: 5,6,7,8,95,6,7,8,9.
The structure of Berland army is organized in such a way that every officer, except for the commander, is a subordinate of the commander of the army.
Formally, let's represent Berland army as a tree consisting of nn vertices, in which vertex uu corresponds to officer uu. The parent of vertex uucorresponds to the direct superior of officer uu. The root (which has index 11) corresponds to the commander of the army.
Berland War Ministry has ordered you to give answers on qq queries, the ii-th query is given as (ui,ki)(ui,ki), where uiui is some officer, and kiki is a positive integer.
To process the ii-th query imagine how a command from uiui spreads to the subordinates of uiui. Typical DFS (depth first search) algorithm is used here.
Suppose the current officer is aa and he spreads a command. Officer aa chooses bb — one of his direct subordinates (i.e. a child in the tree) who has not received this command yet. If there are many such direct subordinates, then aa chooses the one having minimal index. Officer aa gives a command to officer bb. Afterwards, bb uses exactly the same algorithm to spread the command to its subtree. After bb finishes spreading the command, officer aa chooses the next direct subordinate again (using the same strategy). When officer aa cannot choose any direct subordinate who still hasn't received this command, officer aa finishes spreading the command.
Let's look at the following example:
If officer 11 spreads a command, officers receive it in the following order: [1,2,3,5,6,8,7,9,4][1,2,3,5,6,8,7,9,4].
If officer 33 spreads a command, officers receive it in the following order: [3,5,6,8,7,9][3,5,6,8,7,9].
If officer 77 spreads a command, officers receive it in the following order: [7,9][7,9].
If officer 99 spreads a command, officers receive it in the following order: [9][9].
To answer the ii-th query (ui,ki)(ui,ki), construct a sequence which describes the order in which officers will receive the command if the uiui-th officer spreads it. Return the kiki-th element of the constructed list or -1 if there are fewer than kiki elements in it.
You should process queries independently. A query doesn't affect the following queries.
Input
The first line of the input contains two integers nn and qq (2≤n≤2⋅105,1≤q≤2⋅1052≤n≤2⋅105,1≤q≤2⋅105) — the number of officers in Berland army and the number of queries.
The second line of the input contains n−1n−1 integers p2,p3,…,pnp2,p3,…,pn (1≤pi<i1≤pi<i), where pipi is the index of the direct superior of the officer having the index ii. The commander has index 11 and doesn't have any superiors.
The next qq lines describe the queries. The ii-th query is given as a pair (ui,kiui,ki) (1≤ui,ki≤n1≤ui,ki≤n), where uiui is the index of the officer which starts spreading a command, and kiki is the index of the required officer in the command spreading sequence.
Output
Print qq numbers, where the ii-th number is the officer at the position kiki in the list which describes the order in which officers will receive the command if it starts spreading from officer uiui. Print "-1" if the number of officers which receive the command is less than kiki.
You should process queries independently. They do not affect each other.
Example
input
Copy
9 6
1 1 1 3 5 3 5 7
3 1
1 5
3 4
7 3
1 8
1 9
output
Copy
3
6
8
-1
9
4 題意：
給定一個樹， 然後有Q次詢問。 詢問給出U, K。 求以U為根的子樹經過深度優先搜尋的第K個兒子，如果一個節點有多個兒子，按照兒子從小到大的順序，依次通路。
題解：
子樹的DFS序和從根1開始的通路DFS序是一樣的， 是以我們直接求即可。
代碼：
By I_LOVE_YZQ, contest: Codeforces Round #498 (Div. 3), problem: (E) Military Problem, Accepted, #, hack it!
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 7;
int time_tag;
int n, q;
int in[maxn], out[maxn], who[maxn];
vector<int> g[maxn];
struct node
{
int lc, rc, v; //lc,rc分别代表左右兒子編号, v代表這個節點管轄的範圍内的數出現的次數
node () {lc=rc=v=0;}
}t[maxn*40];
int tot;
int a[maxn];
int b[maxn];
int rt[maxn];
int son[maxn];
int build(int l, int r) //初始化
{
int now = ++ tot;
t[now].lc = t[now].rc = t[now].v = 0;
if(l == r) return now;
int mid = (l + r) >> 1;
t[now].lc = build(l, mid);
t[now].rc = build(mid+1, r);
return now;
}
int insert(int last, int l, int r, int pos)
{
int now = ++ tot;
t[now] = t[last];
t[now].v ++;
if(l == r) return now;
int mid = (l + r) >> 1;
if(pos <= mid) t[now].lc = insert(t[last].lc, l, mid, pos);
else t[now].rc = insert(t[last].rc, mid+1, r, pos);
return now;
}
int query(int st, int ed, int l, int r, int k) // 第k小
{
if(l == r) return l;
int num = t[ t[ed].lc ].v - t[ t[st].lc ].v; //兩個版本做差
int mid = (l + r) >> 1;
if(k <= num) return query(t[st].lc, t[ed].lc, l, mid, k);
return query(t[st].rc, t[ed].rc, mid+1, r, k - num);
}
void dfs(int u, int par)
{
son[u] = 1;
++time_tag;
in[u] = time_tag;
who[time_tag] = u;
rt[time_tag] = insert(rt[time_tag-1], 1, n, time_tag);
for(auto v : g[u]) {
if(v != par) {
dfs(v, u);
son[u] += son[v];
}
}
out[u] = time_tag;
}
int main()
{
ios::sync_with_stdio(false), cin.tie(0);
cin >> n >> q;
rt[0] = build(1, n);
for(int i = 2; i <= n; i ++) {
int par;
cin >> par;
g[par].push_back(i);
g[i].push_back(par);
}
dfs(1, -1);
while(q --) {
int p, k;
cin >> p >> k;
if(son[p] < k) {
cout << -1 << '\n';
} else {
cout << who[query(rt[in[p]-1], rt[out[p]], 1, n, k)] << '\n';
}
}
return 0;
}