先把问题简化，怎样求一个点x和y的lca的deep和
显然直接求LCA，但是这样的话，要求多个就不好叠加 于是可以用奇技淫巧：先把x到根的所有点打上标记，那么询问y到根的标记的个数即为答案，这样就可以叠加 所以对于询问，拆成[1,l-1], [1, r]，排序后依次加点覆盖标记即可可以用树链剖分+线段树，或者Orz yyb大佬一样写LCT
代码
表示不想写LCT
# include# define RG register# define IL inline# define Fill(a, b) memset(a, b, sizeof(a))using namespace std;typedef long long ll;const int _(1e5 + 10), __(1e6 + 10), INF(2e9), MOD(201314);IL ll Read(){ char c = '%'; ll x = 0, z = 1; for(; c > '9' || c < '0'; c = getchar()) if(c == '-') z = -1; for(; c >= '0' && c <= '9'; c = getchar()) x = x * 10 + c - '0'; return x * z;}int n, q, cnt, fst[_], to[_], nxt[_], fa[_], son[_], size[_], top[_], deep[_], dfn[_];int sum[__], tag[__], ans[_], z[_];struct Data{ int f, id, type; IL bool operator <(RG Data B) const{ return f < B.f; }} qry[_];IL void Add(RG int u, RG int v){ to[cnt] = v; nxt[cnt] = fst[u]; fst[u] = cnt++; }IL void Dfs1(RG int u){ size[u] = 1; for(RG int e = fst[u]; e != -1; e = nxt[e]){ if(size[to[e]]) continue; deep[to[e]] = deep[u] + 1; fa[to[e]] = u; Dfs1(to[e]); size[u] += size[to[e]]; if(size[to[e]] > size[son[u]]) son[u] = to[e]; }}IL void Dfs2(RG int u, RG int Top){ top[u] = Top; dfn[u] = ++cnt; if(son[u]) Dfs2(son[u], Top); for(RG int e = fst[u]; e != -1; e = nxt[e]) if(!dfn[to[e]]) Dfs2(to[e], to[e]);}IL void Update(RG int x){ sum[x] = (sum[x << 1] + sum[x << 1 | 1]) % MOD; }IL void Pushdown(RG int x, RG int l, RG int r){ if(!tag[x]) return; RG int mid = (l + r) >> 1, ls = x << 1, rs = x << 1 | 1; (sum[ls] += (mid - l + 1) * tag[x]) %= MOD; (sum[rs] += (r - mid) * tag[x]) %= MOD; tag[ls] += tag[x]; tag[rs] += tag[x]; tag[x] = 0;}IL void Modify(RG int x, RG int l, RG int r, RG int L, RG int R){ if(L <= l && R >= r){ (sum[x] += r - l + 1) %= MOD; tag[x]++; return; } Pushdown(x, l, r); RG int mid = (l + r) >> 1; if(L <= mid) Modify(x << 1, l, mid, L, R); if(R > mid) Modify(x << 1 | 1, mid + 1, r, L, R); Update(x);}IL int Query(RG int x, RG int l, RG int r, RG int L, RG int R){ if(L <= l && R >= r) return sum[x]; Pushdown(x, l, r); RG int mid = (l + r) >> 1, Ans = 0; if(L <= mid) Ans = Query(x << 1, l, mid, L, R); if(R > mid) Ans += Query(x << 1 | 1, mid + 1, r, L, R); Update(x); return Ans;}IL void Cover(RG int x, RG int y){ while(top[x] != top[y]){ if(deep[top[x]] < deep[top[y]]) swap(x, y); Modify(1, 1, n, dfn[top[x]], dfn[x]); x = fa[top[x]]; } if(deep[x] < deep[y]) swap(x, y); Modify(1, 1, n, dfn[y], dfn[x]);}IL int Calc(RG int x, RG int y){ RG int Ans = 0; while(top[x] != top[y]){ if(deep[top[x]] < deep[top[y]]) swap(x, y); Ans += Query(1, 1, n, dfn[top[x]], dfn[x]); x = fa[top[x]]; } if(deep[x] < deep[y]) swap(x, y); Ans += Query(1, 1, n, dfn[y], dfn[x]); return Ans;}int main(RG int argc, RG char *argv[]){ n = Read(); q = Read(); Fill(fst, -1); for(RG int i = 2, a; i <= n; ++i) a = Read() + 1, Add(a, i), Add(i, a); Dfs1(1); cnt = 0; Dfs2(1, 1); cnt = 0; for(RG int i = 1; i <= q; ++i){ qry[++cnt].f = Read(); qry[cnt].id = i; qry[cnt].type = -1; qry[++cnt].f = Read() + 1; qry[cnt].id = i; qry[cnt].type = 1; z[i] = Read() + 1; } sort(qry + 1, qry + cnt + 1); for(RG int i = 1, j = 0; i <= cnt; ++i){ while(j < qry[i].f) ++j, Cover(1, j); ans[qry[i].id] += qry[i].type * Calc(1, z[qry[i].id]); } for(RG int i = 1; i <= q; i++) printf("%d\n", (ans[i] % MOD + MOD) % MOD); return 0;}