rt，不会写 spj ，也没找到输出一样的题解

写法是找 dfn 最大/最小 用了三个 st 表

#include<cstdio>
#include<algorithm>
#define INF (0x3f3f3f3f)
using namespace std;

const int MAXN = 300005;

int n, Q;
int lg[MAXN << 1];
struct edge {
	int to, nex; 
}e[MAXN << 1]; int idx, head[MAXN];
inline void add(int u, int v) {
	e[++ idx].to = v;
	e[idx].nex = head[u];
	head[u] = idx;
}
int dep[MAXN], dfn[MAXN];
inline int _min(const int &x, const int &y) {
	return (dfn[x] < dfn[y]) ? x : y;
}
inline int _max(const int &x, const int &y) {
	return (dfn[x] > dfn[y]) ? x : y;
}

namespace Tree {
	int timer, eu[MAXN << 1];
	inline void dfs(int u) {
		eu[dfn[u] = ++ timer] = u;
		if (u == 1) dep[u] = 1;
		for (int i = head[u]; i; i = e[i].nex) {
			int v = e[i].to;
			dep[v] = dep[u] + 1;
			dfs(v); eu[++ timer] = u;
		}
	}
	int f[MAXN << 1][25];
	inline void Init() {
		dep[0] = INF;
		for (int i = 2; i <= timer; ++ i)
			lg[i] = lg[i >> 1] + 1;
		for (int i = 1; i <= timer; ++ i)
			f[i][0] = eu[i];
		for (int j = 1; j <= lg[timer]; ++ j)
			for (int i = 1; i <= timer; ++ i) {
				f[i][j] = f[i][j - 1];
				if (i + (1 << (j - 1)) <= timer)
					f[i][j] = _min(f[i][j], f[(i + (1 << (j - 1)))][j - 1]);
			}
	}
	inline int Get_lca(int u, int v) {
		int l = min(dfn[u], dfn[v]);
		int r = max(dfn[u], dfn[v]);
		int len = lg[r - l + 1];
		return _min(f[l][len], f[r - (1 << len) + 1][len]);
	}
	inline void prew() {
		scanf ("%d%d", &n, &Q);
		for (int i = 2; i <= n; ++ i) {
			int fath;
			scanf ("%d", &fath);
			add(fath, i);
		}
		dfs(1); Init();
	}
}
namespace Arr {
	int lc[MAXN][25];
	int f1[MAXN][25], f2[MAXN][25];
	inline int Get_lca(int l, int r) {
		int len = lg[r - l + 1];
		return Tree::Get_lca(lc[l][len], lc[r - (1 << len) + 1][len]);
	}
	inline int Get_min(int l, int r) {
		int len = lg[r - l + 1];
		return _min(f1[l][len], f1[r - (1 << len) + 1][len]);
	}
	inline int Get_max(int l, int r) {
		int len = lg[r - l + 1];
		return _max(f2[l][len], f2[r - (1 << len) + 1][len]);
	}
	inline void Init() {
		for (int i = 1; i <= n; ++ i)
			lc[i][0] = i, 
			f1[i][0] = f2[i][0] = i;
		for (int j = 1; j <= lg[n]; ++ j)
			for (int i = 1, v; i <= n; ++ i) {
				lc[i][j] = lc[i][j - 1];
				f1[i][j] = f1[i][j - 1];
				f2[i][j] = f2[i][j - 1];
				if ((v = i + (1 << (j - 1))) <= n)
					lc[i][j] = Tree::Get_lca(lc[i][j], lc[v][j - 1]), 
					f1[i][j] = _min(f1[i][j], f1[v][j - 1]), 
					f2[i][j] = _max(f2[i][j], f2[v][j - 1]);
			}
	}
	inline void Solve() {
		int l, r;
		scanf ("%d%d", &l, &r);
		int p1 = Get_min(l, r), u;
		if (p1 == l) u = Get_lca(p1 + 1, r);
		else if (p1 == r) u = Get_lca(l, p1 - 1);
		else u = Tree::Get_lca(Get_lca(l, p1 - 1), Get_lca(p1 + 1, r));
		int p2 = Get_max(l, r), v;
		if (p2 == l) v = Get_lca(p2 + 1, r);
		else if (p2 == r) v = Get_lca(l, p2 - 1);
		else v = Tree::Get_lca(Get_lca(l, p2 - 1), Get_lca(p2 + 1, r));
		printf ("%d %d\n", (dfn[u] > dfn[v]) ? p1 : p2, dep[_max(u, v)] - 1);
	}
}

int main()
{
	Tree::prew();
	Arr::Init();
	while (Q --) Arr::Solve();
	return 0;
}