比较神奇的一道树的题。
做法是离线。想了好久的在线啊。
把询问拆成0~l-1和0~r。挨个从0开始加点。加点就是把从根到这个点的所有点权+1，询问就是询问这个点到根的点权和。好机智的做法。
代码还比较舒服。dfs+树链剖分+树状数组。
#include <cstdio>
#include <memory.h>
#include <algorithm>
using namespace std;
struct edge {
int t;
edge *next;
};
struct query {
int p, v, n, c;
inline query(int p0 = 0, int v0 = 0, int n0 = 0, int c0 = 0) {
p = p0, v = v0, n = n0, c = c0;
}
};
const int maxn = 50009;
const int mod = 201314;
void btChg(int* t, int p, int v) {
while (p < maxn)
(t[p] += v) %= mod, p += (p & -p);
}
int btQry(int* t, int p) {
int s = 0;
while (p)
(s += t[p]) %= mod, p -= (p & -p);
return s;
}
inline bool cmpQuery(const query& a, const query& b) {
return a. p < b. p;
}
edge *head[maxn], *ep;
query q[maxn * 2];
int n, m, fa[maxn], ans[maxn];
int tc, sz[maxn], fc[maxn], ch[maxn], fs[maxn];
int dfo[maxn], dfb[maxn];
int t[maxn], s[maxn];
inline void addEdge(int u, int v) {
ep-> t = v;
ep-> next = head[u];
head[u] = ep ++;
}
void dfs() {
static int stc[maxn];
int tstc = 1, dfn = 0;
stc[1] = 0;
while (tstc) {
int p = stc[tstc --];
dfo[++ dfn] = p;
dfb[p] = dfn;
for (edge* e = head[p]; e; e = e-> next)
if (!dfb[e-> t])
stc[++ tstc] = e-> t;
}
tc = 0;
for (int i = n; i; -- i) {
int p = dfo[i], x = -1;
sz[p] = 1;
for (edge* e = head[p]; e; e = e-> next)
if (dfb[e-> t] > dfb[p]) {
sz[p] += sz[e-> t];
if (x == -1 || sz[e-> t] > sz[x])
x = e-> t;
}
fs[p] = x;
if (x == -1) {
fc[p] = ++ tc;
ch[fc[p]] = p;
}
else {
fc[p] = fc[x];
ch[fc[p]] = p;
}
}
tstc = 1;
stc[1] = 0;
dfn = 0;
memset(dfb, 0, sizeof(dfb));
while (tstc) {
int p = stc[tstc --];
dfo[++ dfn] = p;
dfb[p] = dfn;
for (edge* e = head[p]; e; e = e-> next)
if (e-> t ^ fs[p])
stc[++ tstc] = e-> t;
if (fs[p] > -1)
stc[++ tstc] = fs[p];
}
}
void segChg(int l, int r, int v) {
btChg(t, l, v);
btChg(s, l, l * v % mod);
btChg(t, r + 1, mod - v);
btChg(s, r + 1, mod - (r + 1) * v % mod);
}
int segQry(int l, int r) {
return ((btQry(t, r) * (r + 1) % mod - btQry(s, r)\
- btQry(t, l - 1) * l % mod + btQry(s, l - 1)) % mod + mod) % mod;
}
void ins(int p) {
while (p ^ -1) {
segChg(dfb[ch[fc[p]]], dfb[p], 1);
p = fa[ch[fc[p]]];
}
}
int qry(int p) {
int s = 0;
while (p ^ -1) {
(s += segQry(dfb[ch[fc[p]]], dfb[p])) %= mod;
p = fa[ch[fc[p]]];
}
return s;
}
int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif
memset(head, 0, sizeof(head));
ep = new edge[maxn * 2];
scanf("%d%d", &n, &m);
fa[0] = -1;
for (int i = 1; i < n; ++ i) {
scanf("%d", fa + i);
addEdge(fa[i], i);
}
for (int i = 0; i < m; ++ i) {
int l, r, p;
scanf("%d%d%d", &l, &r, &p);
q[i << 1] = query(l - 1, p, i, -1);
q[(i << 1) | 1] = query(r, p, i, 1);
}
sort(q, q + m * 2, cmpQuery);
dfs();
for (int i = 0, j = 0; j < m * 2;) {
for (; i <= q[j]. p; ++ i)
ins(i);
for (; j < m * 2 && q[j]. p == i - 1; ++ j)
ans[q[j]. n] += q[j]. c * qry(q[j]. v);
}
for (int i = 0; i < m; ++ i)
printf("%d\n", (ans[i] % mod + mod) % mod);
}