题目链接：
题目分析
考虑这样的等价问题，如果我们把一个点 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#include #include #include #include #include #include #include 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 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;}