题意
给出一个 (n) 个节点的有根树（编号为 (0) 到 (n-1)，根节点为 (0)）。
一个点的深度定义为这个节点到根的距离 (+1)。
设 (dep[i]) 表示点 (i) 的深度，(LCA(i,j)) 表示 (i) 与 (j) 的最近公共祖先。
有 (m) 次询问，每次询问给出 l r z，求 (sum_{i=l}^r dep[LCA(i,z)])。
题解
我们考虑这样一件事情，就是说，两个点的 (Lca) 的深度的意义到底是什么，如何才能够快速求的？
在我们不会求 (Lca) 的时候，我们会将一个点一个一个往上爬，并将路径上的点染色。之后我们将另一个点暴力往上跳，第一个染色过的点就是 (Lca)。
我们考虑到这样一件事情，如果我们将一个点到根的路径上每个点数值加 (1)，再求得另一个点到根的路径上的权值和，这不就是 (Lca) 的深度了吗？
于是求解一次询问就相当于对于 (lle xle r)，将 (x) 到根的路径上每个点加一，最后答案就是 (z) 到根的权值和。
由于询问次数很多，不可能每次都这样处理一遍，考虑将询问拆开。
[sum_{i=l}^r dep[LCA(i,z)]=sum_{i=1}^r dep[LCA(i,z)]-sum_{i=1}^{l-1} dep[LCA(i,z)]
]
这样我们就可以在 (O(nlog n)) 复杂度内解决问题啦！
这就叫数据结构二步曲，学习一下，代码我现在放下。
#define Maxn 50005
#define pb push_back
#define mod 201314
typedef long long ll;
int n,m,tot,Time,cnt;
int ans[Maxn];
int dfn[Maxn],tp[Maxn],fa[Maxn],dep[Maxn],siz[Maxn],bigson[Maxn];
int hea[Maxn],nex[Maxn],ver[Maxn];
struct TREE { int laz,sum; }tree[Maxn<<2];
struct Query { int num,z,opt; };
vector<Query> q[Maxn];
void dfs1(int x)
{
siz[x]=1;
for(int i=hea[x];i;i=nex[i])
{
fa[ver[i]]=x,dep[ver[i]]=dep[x]+1;
dfs1(ver[i]),siz[x]+=siz[ver[i]];
if(siz[ver[i]]>siz[bigson[x]]) bigson[x]=ver[i];
}
}
void dfs2(int x,int T)
{
tp[x]=T,dfn[x]=++Time;
if(bigson[x]) dfs2(bigson[x],T);
for(int i=hea[x];i;i=nex[i])
{
if(ver[i]==bigson[x]) continue;
dfs2(ver[i],ver[i]);
}
}
void pushdown(int p,int nl,int nr)
{
int mid=(nl+nr)>>1;
tree[p<<1].laz=(tree[p<<1].laz+tree[p].laz)%mod;
tree[p<<1|1].laz=(tree[p<<1|1].laz+tree[p].laz)%mod;
tree[p<<1].sum=(tree[p<<1].sum+1ll*tree[p].laz*(mid-nl+1)%mod)%mod;
tree[p<<1|1].sum=(tree[p<<1|1].sum+1ll*tree[p].laz*(nr-mid)%mod)%mod;
tree[p].laz=0;
}
void add(int p,int nl,int nr,int l,int r)
{
if(nl>=l && nr<=r) { tree[p].laz++,tree[p].sum+=(nr-nl+1); return; }
pushdown(p,nl,nr);
int mid=(nl+nr)>>1;
if(mid>=l) add(p<<1,nl,mid,l,r);
if(mid<r) add(p<<1|1,mid+1,nr,l,r);
tree[p].sum=(tree[p<<1].sum+tree[p<<1|1].sum)%mod;
}
int query(int p,int nl,int nr,int l,int r)
{
if(nl>=l && nr<=r) return tree[p].sum;
pushdown(p,nl,nr);
int mid=(nl+nr)>>1,ret=0;
if(mid>=l) ret=(ret+query(p<<1,nl,mid,l,r))%mod;
if(mid<r) ret=(ret+query(p<<1|1,mid+1,nr,l,r))%mod;
tree[p].sum=(tree[p<<1].sum+tree[p<<1|1].sum)%mod;
return ret;
}
inline void add_path(int x)
{
while(tp[x]!=tp[1]) add(1,1,n,dfn[tp[x]],dfn[x]),x=fa[tp[x]];
add(1,1,n,dfn[1],dfn[x]);
}
inline int query_path(int x)
{
int ret=0;
while(tp[x]!=tp[1]) ret=(ret+query(1,1,n,dfn[tp[x]],dfn[x]))%mod,x=fa[tp[x]];
ret=(ret+query(1,1,n,dfn[1],dfn[x]))%mod;
return ret;
}
inline void add_edge(int x,int y){ ver[++tot]=y,nex[tot]=hea[x],hea[x]=tot; }
int main()
{
n=rd(),m=rd();
for(int i=2,f;i<=n;i++) f=rd()+1,add_edge(f,i);
dfs1(1),dfs2(1,0); // 记得输入的下标从 0 开始
for(int i=1,l,r,z;i<=m;i++)
{
l=rd()+1,r=rd()+1,z=rd()+1;
q[l-1].pb((Query){i,z,-1});
q[r].pb((Query){i,z,1});
}
for(int i=1;i<=n;i++)
{
add_path(i);
for(Query j:q[i])
ans[j.num]=(ans[j.num]+j.opt*query_path(j.z)%mod+mod)%mod;
}
for(int i=1;i<=m;i++) printf("%d
",ans[i]);
return 0;
}