【题目链接】
【算法】
考虑求lca(x,y)的深度
我们可以将从根到x路径上的点都打上标记，然后，询问y到根上路径的权值和
那么，求sigma(depth(lca(i,z)))（l <= i <= r )，我们可以将区间[l,r]中的点依次打上标记，然后，询问点z到根路径
上的权值和
因为此题有多组询问，显然在线很难做，因此，我们考虑离线计算答案
求sigma(depth(lca(i,z))) (l <= i <= r)，我们可以转化为
sigma(depth(lca(i,z))) ( 0 <= i <= r) - sigma(depth(lca(i,z))) (0 <= i <= l - 1)
那么，树链剖分/动态树都可以解决这道题，树链剖分的时间复杂度是O((n + q) log(n)^2)的，而动态树的时间复杂度是 O((n + q) log(n))的
【代码】
由于笔者太弱，不会动态树，所以这份代码是树链剖分的写法
#include<bits/stdc++.h> using namespace std; #define MAXM 50010 const int P = 201314; struct Edge { int to,nxt; } e[MAXM]; struct Query { int pos,opt,z,id; } q[MAXM*2]; int i,n,m,f,timer,tot,cnt,now,l,r,z; int dfn[MAXM],size[MAXM],top[MAXM],head[MAXM],son[MAXM],ans[MAXM],fa[MAXM]; struct SegmentTree { struct Node { int l,r; int sum,tag; } Tree[MAXM*4]; inline void build(int index,int l,int r) { int mid; Tree[index].l = l; Tree[index].r = r; Tree[index].sum = Tree[index].tag = 0; if (l == r) return; mid = (l + r) >> 1; build(index<<1,l,mid); build(index<<1|1,mid+1,r); } inline void pushdown(int index) { int l = Tree[index].l,r = Tree[index].r; int mid = (l + r) >> 1; if (Tree[index].tag) { Tree[index<<1].sum = (Tree[index<<1].sum + (mid - l + 1) * Tree[index].tag) % P; Tree[index<<1|1].sum = (Tree[index<<1|1].sum + (r - mid) * Tree[index].tag) % P; Tree[index<<1].tag = (Tree[index<<1].tag + Tree[index].tag) % P; Tree[index<<1|1].tag = (Tree[index<<1|1].tag + Tree[index].tag) % P; Tree[index].tag = 0; } } inline void update(int index) { Tree[index].sum = (Tree[index<<1].sum + Tree[index<<1|1].sum) % P; } inline void modify(int index,int l,int r,int val) { int mid; if (Tree[index].l == l && Tree[index].r == r) { Tree[index].sum = (Tree[index].sum + (r - l + 1) * val) % P; Tree[index].tag = (Tree[index].tag + val) % P; return; } pushdown(index); mid = (Tree[index].l + Tree[index].r) >> 1; if (mid >= r) modify(index<<1,l,r,val); else if (mid + 1 <= l) modify(index<<1|1,l,r,val); else { modify(index<<1,l,mid,val); modify(index<<1|1,mid+1,r,val); } update(index); } inline int query(int index,int l,int r) { int mid; if (Tree[index].l == l && Tree[index].r == r) return Tree[index].sum; pushdown(index); mid = (Tree[index].l + Tree[index].r) >> 1; if (mid >= r) return query(index<<1,l,r); else if (mid + 1 <= l) return query(index<<1|1,l,r); else return (query(index<<1,l,mid) + query(index<<1|1,mid+1,r)) % P; } } T; inline bool cmp(Query a,Query b) { return a.pos < b.pos; } inline void add(int u,int v) { tot++; e[tot] = (Edge){v,head[u]}; head[u] = tot; } inline void dfs1(int u) { int i,v; size[u] = 1; for (i = head[u]; i; i = e[i].nxt) { v = e[i].to; dfs1(v); size[u] += size[v]; if (size[v] > size[son[u]] || !son[u]) son[u] = v; } } inline void dfs2(int u,int tp) { int i,v; top[u] = tp; dfn[u] = ++timer; if (son[u]) dfs2(son[u],tp); for (i = head[u]; i; i = e[i].nxt) { v = e[i].to; if (son[u] != v) dfs2(v,v); } } inline void modify(int pos) { int tp = top[pos]; while (tp) { T.modify(1,dfn[tp],dfn[pos],1); pos = fa[tp]; tp = top[pos]; } T.modify(1,1,dfn[pos],1); } inline int query(int pos) { int tp = top[pos],ans = 0; while (tp) { ans = (ans + T.query(1,dfn[tp],dfn[pos])) % P; pos = fa[tp]; tp = top[pos]; } ans = (ans + T.query(1,1,dfn[pos])) % P; return ans; } int main() { scanf("%d%d",&n,&m); for (i = 1; i < n; i++) { scanf("%d",&fa[i]); add(fa[i],i); } dfs1(0); dfs2(0,0); T.build(1,1,timer); for (i = 1; i <= m; i++) { scanf("%d%d%d",&l,&r,&z); if (l != 0) q[++cnt] = (Query){l-1,-1,z,i}; q[++cnt] = (Query){r,1,z,i}; } sort(q+1,q+cnt+1,cmp); now = -1; for (i = 1; i <= cnt; i++) { while (now + 1 <= q[i].pos) { now++; modify(now); } if (q[i].opt == 1) ans[q[i].id] = (ans[q[i].id] + query(q[i].z)) % P; else ans[q[i].id] = (ans[q[i].id] - query(q[i].z) + P) % P; } for (i = 1; i <= m; i++) printf("%d ",ans[i]); return 0; }