前置知识：树剖、差分
题意
给定一个 \(n\) 个节点的有根树树，根为 \(1\)。有 \(m\) 个询问，每个询问给定 \(l, r, z\)，求 \(\sum\limits_{i = l}^r dep[\textrm{LCA}(i, z)]\)。其中 \(dep[x]\) 表示 \(x\) 的深度，有 \(dep[1] = 1\)。
题解
式子中的 \(dep\) 不太好算，考虑转化成形式化的式子。对于单个询问 \((l, r, z)\)，假设 \(a_1, a_2, \cdots, a_k\) 表示 \(1 \to z\) 路径上的点编号，显然有 \(dep[a_i] = i\)；再假设 \(S_x(l, r)\) 表示 \(x\) 子树内编号在 \([l, r]\) 中的点数量，那么：
\[\begin{aligned} &\sum\limits_{i = l}^r dep[\textrm{LCA}(i, z)]\\ =& k \times S_{a_k}(l, r) + \sum\limits_{i = 1}^{k - 1} i \times (S_{a_i}(l, r) - S_{a_{i + 1}}(l, r)) \\ \end{aligned} \]将每个 \(S_{a_i}(l, r)\) 的系数化简一下，得到：
\[\begin{aligned} &k \times S_{a_k}(l, r) + \sum\limits_{i = 1}^{k - 1} i \times (S_{a_i}(l, r) - S_{a_{i + 1}}(l, r)) \\ =&\sum\limits_{i = 1}^k S_{a_i}(l, r) \end{aligned} \]这个式子不太能直接做，差分一下，得到：
\[\begin{aligned} &\sum\limits_{i = 1}^k S_{a_i}(l, r)\\ =&\sum\limits_{i = 1}^k \left(S_{a_i}(1, r) - S_{a_i}(1, l - 1)\right) \end{aligned} \]接着考虑计算一个前缀的答案，将询问离线下来，然后从 \(1\) 到 \(n\) 一个一个插入。对于 \(i\)，可以发现 \(i\) 的出现只会对 \(1 \to i\) 这条链上的点的 \(S\) 产生影响，所以直接链加。而查询的时候，直接查询链和即可。这两个东西可以树剖做。复杂度 \(O(n \log^2 n)\)。
code:
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
const int N = 5E4 + 5;
int n, m, son[N], tot, dfn[N], sz[N], top[N], yf[N], dep[N], wt[N];
i64 Ans[N];
vector <tuple <int, int, int>> v[N];
vector <int> G[N];
void dfs1(int x, int fa) {
sz[x] = 1; pair <int, int> mx = make_pair(0, 0);
for (auto v : G[x]) {
if (v == fa) continue;
dep[v] = dep[x] + 1; yf[v] = x;
dfs1(v, x);
sz[x] += sz[v];
mx = max(mx, make_pair(sz[v], v));
} son[x] = mx.second;
}
void dfs2(int x, int topf) {
wt[dfn[x] = ++tot] = x; top[x] = topf;
if (!son[x]) return ;
dfs2(son[x], topf);
for (auto v : G[x]) {
if (v == yf[x] || v == son[x]) continue ;
dfs2(v, v);
}
}
struct segt {
struct node {
int l, r;
i64 sum, tag;
} t[N << 2];
int lson(int x) {return x << 1;}
int rson(int x) {return x << 1 | 1;}
void pushup(int x) {t[x].sum = t[lson(x)].sum + t[rson(x)].sum;}
void build(int x, int l, int r) {
t[x].l = l; t[x].r = r; t[x].tag = t[x].sum = 0;
if (l == r) return ;
int mid = (l + r) >> 1;
build(lson(x), l, mid);
build(rson(x), mid + 1, r);
pushup(x);
}
void upd(int x, i64 val) {t[x].tag += val; t[x].sum += val * (t[x].r - t[x].l + 1);}
void pushdown(int x) {
upd(lson(x), t[x].tag); upd(rson(x), t[x].tag);
t[x].tag = 0;
}
void update(int x, int L, int R) {
if (t[x].l >= L && t[x].r <= R) return upd(x, 1);
int mid = (t[x].l + t[x].r) >> 1; pushdown(x);
if (L <= mid) update(lson(x), L, R);
if (R > mid) update(rson(x), L, R);
pushup(x);
}
i64 query(int x, int L, int R) {
if (t[x].l >= L && t[x].r <= R) return t[x].sum;
int mid = (t[x].l + t[x].r) >> 1; i64 res = 0; pushdown(x);
if (L <= mid) res += query(lson(x), L, R);
if (R > mid) res += query(rson(x), L, R);
return res;
}
} t;
void update(int x) {
while (top[x] != 1) {
t.update(1, dfn[top[x]], dfn[x]);
x = yf[top[x]];
}
t.update(1, 1, dfn[x]);
}
i64 query(int x) {
i64 res = 0;
while (top[x] != 1) {
res += t.query(1, dfn[top[x]], dfn[x]);
x = yf[top[x]];
} return res + t.query(1, 1, dfn[x]);
}
signed main(void) {
ios :: sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n >> m;
for (int i = 2; i <= n; ++i) {
int p; cin >> p; ++p;
G[i].emplace_back(p);
G[p].emplace_back(i);
} dep[1] = 1;
dfs1(1, 0); dfs2(1, 1); t.build(1, 1, n);
for (int i = 1; i <= m; ++i) {
int l, r, z; cin >> l >> r >> z;
++z; ++l, ++r;
v[r].emplace_back(1, i, z);
v[l - 1].emplace_back(-1, i, z);
}
for (int i = 1; i <= n; ++i) {
update(i);
for (auto [val, id, x] : v[i])
Ans[id] += val * query(x);
}
for (int i = 1; i <= m; ++i)
cout << Ans[i] % 201314 << '\n';
return 0;
}