题目传送门(BZOJ)
>原文链接<

题解 :

转自THU爷 gconeice 的题解,说的很明白

  1. 显然,暴力求解的复杂度是无法承受的。考虑这样的一种暴力,我们把 $z$ 到根上的点全部打标记,对于 $l$ 到 $r$ 之间的点,向上搜索到第一个有标记的点求出它的深度统计答案。观察到,深度其实就是上面有几个已标记了的点(包括自身)。所以,我们不妨把 $z$ 到根的路径上的点全部+1,对于 $l$ 到 $r$ 之间的点询问他们到根路径上的点权和。仔细观察上面的暴力不难发现,实际上这个操作具有叠加性,且可逆。

也就是说我们可以对于 l 到 r 之间的点 i,将 i 到根的路径上的点全部 +1, 转而询问 z 到根的路径上的点(包括自身)的权值和就是这个询问的答案。

  1. 把询问差分下,也就是用 $[1, r] − [1, l − 1]$ 来计算答案,那么现在我们就有一个明显的解法。从 $0$ 到 $n − 1$ 依次插入点 $i$,即将 $i$ 到根的路径上的点全部+1。离线询问答案即可。我们现在需要一个数据结构来维护路径加和路径求和,显然树链剖分或LCT均可以完成这个任务。树链剖分的复杂度为 $O((n + q)· log n · log n)$,LCT的复杂度为 $O((n + q)· log n)$,均可以完成任务。

我写这题的时候忘记模了,咋调都调不出来 Orz

代码 :

#include <map>#include <queue>#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#define ls p << 1#define rs p << 1|1#define mi ((l+r)>>1)#define rev(i, p) for(Edge *i = h[p]; i; i = i->next)#define nc() (p1==p2&&(p2=(p1=buf)+fread(buf, 1, 100000, stdin), p1==p2)?EOF:*p1++)using namespace std;char buf[100000], *p1, *p2;inline int rd() { int x = 0; char ch = nc(); while(!isdigit(ch)) ch = nc(); while(isdigit(ch)) x = ((x+(x<<2))<<1)+(ch^48), ch = nc(); return x;}const int N = 101000;const int P = 201314;struct Edge { int to, val; Edge *next;}*h[N],e[N<<1];inline void Add_Edge(int u, int v, int w = 0) { static int _ = 0; Edge *tmp = &e[++_]; tmp->to = v; tmp->val = w; tmp->next = h[u]; h[u] = tmp;}struct Query { int l, z, opt, id; bool operator < (const Query A) const { return l < A.l; } }q[N<<1];int siz[N], top[N], fa[N], dep[N], son[N], cnt;int ans[N], idx[N], t[N<<2], laz[N<<2], n, Q;void dfs(int p) { dep[p] = dep[fa[p]]+1; siz[p] = 1; rev(i, p) if(i->to != fa[p]) { fa[i->to] = p; dfs(i->to); siz[p] += siz[i->to]; if(siz[i->to] > siz[son[p]]) son[p] = i->to; }}void dfs(int p, int t) { idx[p] = ++*idx; top[p] = t; if(son[p]) dfs(son[p], t); rev(i, p) if(i->to != fa[p] && i->to != son[p]) { dfs(i->to, i->to); }}inline void pd(int l, int r, int p) { if(laz[p]) { int tmp = laz[p]; (t[ls] += tmp*(mi-l+1)) %= P; (t[rs] += tmp*(r-mi)) %= P; (laz[ls] += tmp) %= P; (laz[rs] += tmp) %= P; laz[p] = 0; }}void change(int l, int r, int p, int x, int y, int c) { pd(l, r, p); if(x <= l && y >= r) { laz[p] = c; (t[p] += (r-l+1)*c) %= P; return ; } if(x <= mi) change(l, mi, ls, x, y, c); if(y > mi) change(mi+1, r, rs, x, y, c); t[p] = (t[ls]+t[rs])%P;}inline void insert(int x) { while(x) { change(1, n, 1, idx[top[x]], idx[x], 1); x = fa[top[x]]; }}int query(int l, int r, int p, int x, int y) { pd(l, r, p); if(x <= l && y >= r) return t[p]; int ret = 0; if(x <= mi) ret += query(l, mi, ls, x, y); if(y > mi) ret += query(mi+1, r, rs, x, y); return ret;}inline int query(int x) { int ret = 0; while(x) { (ret += query(1, n, 1, idx[top[x]], idx[x])) %= P; x = fa[top[x]]; } return ret;}int main() { n = rd(), Q = rd(); for(int i = 2; i <= n; i ++ ) { int u = rd()+1; Add_Edge(i, u), Add_Edge(u, i); } for(int i = 1; i <= Q; i ++ ) { int l = rd(), r = rd()+1, z = rd()+1; q[++cnt].l = l, q[cnt].z = z, q[cnt].opt = -1, q[cnt].id = i; q[++cnt].l = r, q[cnt].z = z, q[cnt].opt = 1, q[cnt].id = i; } sort(q+1, q+cnt+1); dfs(1), dfs(1, 1); int now = 0; for(int i = 1; i <= cnt; i ++ ) { while(now < q[i].l && now <= n) insert(++now); ans[q[i].id] += q[i].opt*query(q[i].z); } for(int i = 1; i <= Q; i ++ ) printf("%d\n", (ans[i]%P+P)%P);}