题目链接： BZOJ - 3626
题目分析
考虑这样的等价问题，如果我们把一个点 x 到 Root 的路径上每个点的权值赋为 1 ，其余点的权值为 0，那么从 LCA(x, y) 的 Depth 就是从 y 到 Root 的路径上的点权和。
这个方法是可以叠加的，这是非常有用的一点。如果我们把 [l, r] 的每个点到 Root 的路径上所有点的权值 +1，再求出从 c 到 Root 的路径点权和，即为 [l, r] 中所有点与 c 的 LCA 的 Depth 和。
不仅满足可加性，还满足可减性，这就更好了！
那么我们就可以对每个询问 [l, r] 做一个差分，用 Query(r) - Query(l - 1) 作为答案。这样就有一种离线算法：将 n 个点依次操作，将其到 Root 的路径上的点权值 +1 ，然后如果这个点是某个询问的 l - 1 或 r ，就用那个询问的 c 求一下到 Root 的路径和，算入答案中。
Done！
写代码的时候忘记 % Mod 真是弱...
代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <queue>
#include <vector> using namespace std; const int MaxN = 50000 + 5, Mod = 201314; int n, m, Index;
int Father[MaxN], Depth[MaxN], Size[MaxN], Son[MaxN], Top[MaxN], Pos[MaxN];
int T[MaxN * 4], D[MaxN * 4], Len[MaxN * 4], Ans[MaxN], Q[MaxN]; vector<int> BA[MaxN], EA[MaxN]; struct Edge
{
int v;
Edge *Next;
} E[MaxN], *P = E, *Point[MaxN]; inline void AddEdge(int x, int y) {
++P; P -> v = y;
P -> Next = Point[x]; Point[x] = P;
} int DFS_1(int x, int Dep) {
Depth[x] = Dep;
Size[x] = 1;
int SonSize, MaxSonSize;
SonSize = MaxSonSize = 1;
for (Edge *j = Point[x]; j; j = j -> Next) {
SonSize = DFS_1(j -> v, Dep + 1);
if (SonSize > MaxSonSize) {
MaxSonSize = SonSize;
Son[x] = j -> v;
}
Size[x] += SonSize;
}
return Size[x];
} void DFS_2(int x) {
if (x == Son[Father[x]]) Top[x] = Top[Father[x]];
else Top[x] = x;
Pos[x] = ++Index;
if (Son[x] != 0) DFS_2(Son[x]);
for (Edge *j = Point[x]; j; j = j -> Next)
if (j -> v != Son[x]) DFS_2(j -> v);
} void Build_Tree(int x, int s, int t) {
Len[x] = t - s + 1;
D[x] = T[x] = 0;
if (s == t) return;
int m = (s + t) >> 1;
Build_Tree(x << 1, s, m);
Build_Tree(x << 1 | 1, m + 1, t);
} inline void Update(int x) {
T[x] = T[x << 1] + T[x << 1 | 1];
T[x] %= Mod;
} inline void Paint(int x, int Num) {
T[x] += Num * Len[x];
T[x] %= Mod;
D[x] += Num;
D[x] %= Mod;
} inline void PushDown(int x) {
if (D[x] == 0) return;
Paint(x << 1, D[x]);
Paint(x << 1 | 1, D[x]);
D[x] = 0;
} void Add(int x, int s, int t, int l, int r) {
if (l <= s && r >= t) {
Paint(x, 1);
return;
}
PushDown(x);
int m = (s + t) >> 1;
if (l <= m) Add(x << 1, s, m, l, r);
if (r >= m + 1) Add(x << 1 | 1, m + 1, t, l, r);
Update(x);
} void EAdd(int x) {
int fx;
fx = Top[x];
while (fx != 1) {
Add(1, 1, n, Pos[fx], Pos[x]);
x = Father[fx];
fx = Top[x];
}
Add(1, 1, n, Pos[1], Pos[x]);
} int Get(int x, int s, int t, int l, int r) {
if (l <= s && r >= t) return T[x];
int ret = 0;
PushDown(x);
int m = (s + t) >> 1;
if (l <= m) ret += Get(x << 1, s, m, l, r);
if (r >= m + 1) ret += Get(x << 1 | 1, m + 1, t, l, r);
return ret % Mod;
} int EGet(int x) {
int ret = 0, fx;
fx = Top[x];
while (fx != 1) {
ret += Get(1, 1, n, Pos[fx], Pos[x]);
ret %= Mod;
x = Father[fx];
fx = Top[x];
}
ret += Get(1, 1, n, Pos[1], Pos[x]);
return ret % Mod;
} int main()
{
scanf("%d%d", &n, &m);
int a, b, c;
for (int i = 2; i <= n; ++i) {
scanf("%d", &a);
++a;
Father[i] = a;
AddEdge(a, i);
}
DFS_1(1, 1);
Index = 0;
DFS_2(1);
Build_Tree(1, 1, n);
for (int i = 1; i <= m; ++i) {
scanf("%d%d%d", &a, &b, &c);
++a; ++b; ++c;
Q[i] = c;
BA[a - 1].push_back(i);
EA[b].push_back(i);
}
for (int i = 1; i <= n; ++i) {
EAdd(i);
for (int j = 0; j < BA[i].size(); ++j)
Ans[BA[i][j]] -= EGet(Q[BA[i][j]]);
for (int j = 0; j < EA[i].size(); ++j)
Ans[EA[i][j]] += EGet(Q[EA[i][j]]);
}
for (int i = 1; i <= m; ++i) printf("%d\n", (Ans[i] + Mod) % Mod);
return 0;
}