paste_3fbg3m9k

注意：本页面是由自动化程序生成的剪贴板存档。

#include <cstdio>
#include <vector>
#define N 50001
std::vector<int> G[N];
int n, fa[N], son[N], sz[N];
void dfsS(int u) {
	sz[u] = 1;
	for (int v : G[u]) {
		dfsS(v);
		sz[u] += sz[v];
		if (sz[v] > sz[son[u]]) son[u] = v;
	}
}
int b[N], bs[N], l[N], r[N], f[N], ss[N];
int cbuild(int bl, int br) {
	int x = bl, y = br;
	while (y-x > 1) {
		int mid = (x+y) >> 1;
		if (2*(bs[mid]-bs[bl]) <= bs[br]-bs[bl]) x = mid;
		else y = mid;
	}
	y = b[x];
	ss[y] = br-bl;
	if (bl < x) {l[y] = cbuild(bl, x); f[l[y]] = y; }
	if (x+1 < br) {r[y] = cbuild(x+1, br); f[r[y]] = y; }
	return y;
}
int build(int x) {
	int y = x;
	do for (int v : G[y])
		if (v != son[y])
			f[build(v)] = y;
	while (y = son[y]);
	y = 0;
	do {
		b[y++] = x; 
		bs[y] = bs[y-1] + sz[x] - sz[son[x]];
	} while (x = son[x]);
	return cbuild(0, y);
}
int a[N], s[N];
void add(int x) {
	bool t = true; int z = 0;
	while (x) {
		s[x] += z;
		if (t) {
			a[x]++; if (r[x]) a[r[x]]--;
			z += 1 + ss[l[x]];
			s[x] -= ss[r[x]];
		}
		t = (x != l[f[x]]);
		if (t && x != r[f[x]]) z = 0;
		x = f[x];
	}
}
int query(int x) {
	int ret = 0;
	bool t = true; int z = 0;
	while (x) {
		if (t) {
			ret += s[x] - s[r[x]];
			ret -= 1ll * ss[r[x]] * a[r[x]];
			z += 1 + ss[l[x]];
		}
		ret += 1ll * z * a[x];
		t = (x != l[f[x]]);
		if (t && x != r[f[x]]) z = 0;
		x = f[x];
	}
	return ret;
}
int q, p[N], ans[N];
std::vector<int> n1[N], n2[N];
int main() {
	scanf("%d%d", &n, &q);
	for (int i = 2; i <= n; i++) {
		scanf("%d", fa+i); fa[i]++;
		G[fa[i]].push_back(i);
	}
	dfsS(1);
	build(1);
	for (int i = 0, x, y; i < q; i++) {
		scanf("%d%d%d", &x, &y, p+i); y++; p[i]++;
		if (x) n1[x].push_back(i);
		n2[y].push_back(i);
	}
	for (int i = 1; i <= n; i++) {
		add(i);
		for (int v : n1[i])
			ans[v] -= query(p[v]);
		for (int v : n2[i])
			ans[v] += query(p[v]);
	}
	for (int i = 0; i < q; i++)
		printf("%d\n", ans[i] % 201314);
}