1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
| #include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const int N = 1e5 + 10;
const ll mod = 1e9 + 7;
int n, q;
int a[N], clk, id[N], fa[N];
vector<int>G[N];
int siz[N], son[N], topf[N], dep[N];
void dfs(int u) {
siz[u] = 1;
for (int v : G[u]) {
dep[v] = dep[u] + 1;
dfs(v);
siz[u] += siz[v];
if (siz[v] > siz[son[u]])son[u] = v;
}
}
void dfs2(int u, int topfa) {
topf[u] = topfa;
a[u] = ++clk; id[clk] = u;
if (!son[u])return;
dfs2(son[u], topfa);
for (int v : G[u]) {
if (!topf[v])dfs2(v, v);
}
}
int LCA(int u, int v) {
while (topf[u] ^ topf[v]) {
dep[topf[u]] < dep[topf[v]] ? v = fa[topf[v]] : u = fa[topf[u]];
}
return dep[u] < dep[v] ? u : v;
}
#define mid ((l+r)>>1)
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
int mx[N << 2], mn[N << 2];
void up(int rt) {
mx[rt] = max(mx[rt << 1], mx[rt << 1 | 1]);
mn[rt] = min(mn[rt << 1], mn[rt << 1 | 1]);
}
void build(int l, int r, int rt) {
if (l == r) {
mn[rt] = mx[rt] = a[l];
return;
}
build(lson);
build(rson);
up(rt);
}
void cg(int q, int x, int l, int r, int rt) {
if (l == r) {
if (x == -1) {
mn[rt] = INF;
mx[rt] = 0;
}
else mn[rt] = mx[rt] = x;
return;
}
if (q <= mid)cg(q, x, lson);
else cg(q, x, rson);
up(rt);
}
int qrymn(int ql, int qr, int l, int r, int rt) {
if (ql <= l && qr >= r)return mn[rt];
int res = INF;
if (ql <= mid)res = min(res, qrymn(ql, qr, lson));
if (qr > mid)res = min(res, qrymn(ql, qr, rson));
return res;
}
int qrymx(int ql, int qr, int l, int r, int rt) {
if (ql <= l && qr >= r)return mx[rt];
int res = 0;
if (ql <= mid)res = max(res, qrymx(ql, qr, lson));
if (qr > mid)res = max(res, qrymx(ql, qr, rson));
return res;
}
int main() {
scanf("%d%d", &n, &q);
memset(mn, 0x3f, sizeof(mn));
memset(mx, 0, sizeof(mx));
for (int i = 2; i <= n; i++) {
scanf("%d", &fa[i]);
G[fa[i]].push_back(i);
}
dfs(1);
dfs2(1, 1);
build(1, n, 1);
while (q--) {
int l, r;
scanf("%d%d", &l, &r);
int x = id[qrymn(l, r, 1, n, 1)], y = id[qrymx(l, r, 1, n, 1)];
if (r == l + 1) {
if (dep[x] >= dep[y])printf("%d %d\n", y, dep[x]);
else printf("%d %d\n", x, dep[y]);
}
else {
cg(x, -1, 1, n, 1);
int tx = id[qrymn(l, r, 1, n, 1)];
int lca1 = LCA(tx, y);
cg(x, a[x], 1, n, 1);
cg(y, -1, 1, n, 1);
int ty = id[qrymx(l, r, 1, n, 1)];
int lca2 = LCA(x, ty);
cg(y, a[y], 1, n, 1);
if (dep[lca1] > dep[lca2]) {
printf("%d %d\n", x, dep[lca1]);
}
else {
printf("%d %d\n", y, dep[lca2]);
}
}
}
return 0;
}
|
