Description
给出一个n个节点的有根树（编号为0到n-1，根节点为0）。一个点的深度定义为这个节点到根的距离+1。
设dep[i]表示点i的深度，LCA(i,j)表示i与j的最近公共祖先。
有q次询问，每次询问给出l r z，求sigma_{l<=i<=r}dep[LCA(i,z)]。
（即，求在[l,r]区间内的每个节点i与z的最近公共祖先的深度之和）
Input
第一行2个整数n q。
接下来n-1行，分别表示点1到点n-1的父节点编号。
接下来q行，每行3个整数l r z。
Output
输出q行，每行表示一个询问的答案。每个答案对201314取模输出
Sample Input
0
0
1
1
1 4 3
1 4 2
Sample Output
5
HINT
共5组数据，n与q的规模分别为10000,20000,30000,40000,50000。
Source
正解：树链剖分+线段树
解题报告：
我这种蒟蒻一看到题目第一反应就是打暴力，真是没戏了。
想了20分钟没想出来就弃疗了，直接看了hzwer神犇的题解，%%%hzwer：http://hzwer.com/3891.html
其实我只看了一眼那个结论我马上就会打了，瞬间变水题。关键是操作具有很多奇奇怪怪的性质，而且转化成求路径上的点权和。
正版推导：
考虑这样的一种暴力，我们把 z 到根上的点全部打标记，对于 l 到 r 之间的点，向上搜索到第一个有标记的点求出它的深度统计答案。观察到，深度其实就是上面有几个已标记了的点（包括自身）。所以，我们不妨把 z 到根的路径上的点全部 +1，对于 l 到 r 之间的点询问他们到根路径上的点权和。仔细观察上面的暴力不难发现，实际上这个操作具有叠加性，且可逆。也就是说我们可以对于 l 到 r 之间的点 i，将 i 到根的路径上的点全部 +1, 转而询问 z 到根的路径上的点（包括自身）的权值和就是这个询问的答案。把询问差分下，也就是用 [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)，均可以完成任务。至此，题目已经被我们完美解决。
//It is made by jump~
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <ctime>
#include <vector>
#include <queue>
#include <map>
#include <set>
using namespace std;
typedef long long LL;
const int MAXN = ;
const int MOD = ;
const int MAXQ = ;
int n,q,ecnt;
int first[MAXN],next[MAXN*],to[MAXN*];
int father[MAXN],top[MAXN],son[MAXN],size[MAXN],deep[MAXN],id[MAXN],pre[MAXN];
int ql,qr,daan; struct wen{
int pos,z,id,ans;
}a[MAXQ]; struct node{
int sum,lazy,l,r,size;
}jump[MAXN*]; inline int getint()
{
int w=,q=;
char c=getchar();
while((c<'' || c>'') && c!='-') c=getchar();
if (c=='-') q=, c=getchar();
while (c>='' && c<='') w=w*+c-'', c=getchar();
return q ? -w : w;
} inline void dfs(int x,int fa){
size[x]=;
for(int i=first[x];i;i=next[i]) {
int v=to[i]; deep[v]=deep[x]+;
dfs(v,x);
size[x]+=size[v];
if(size[v]>size[son[x]]) son[x]=v;
}
} inline void dfs2(int x,int fa){
id[x]=++ecnt; pre[ecnt]=x;
if(son[x]) top[son[x]]=top[x],dfs2(son[x],x);
for(int i=first[x];i;i=next[i]) {
int v=to[i];
if(v!=son[x]) {
top[v]=v;
dfs2(v,x);
}
}
} inline bool cmp(wen q,wen qq){ return q.pos<qq.pos; }
inline bool ccmp(wen q,wen qq){ return q.id<qq.id; } inline void pushdown(int x){
if(jump[x].size==) return ;
if(jump[x].lazy) {
int lc=x*,rc=lc+;
jump[lc].lazy+=jump[x].lazy;jump[rc].lazy+=jump[x].lazy;
jump[lc].sum+=jump[x].lazy*jump[lc].size;jump[rc].sum+=jump[x].lazy*jump[rc].size;
jump[x].lazy=;
}
} inline void update(int root,int l,int r){
pushdown(root);
if(ql<=l && r<=qr) {
jump[root].lazy++;
jump[root].sum+=jump[root].size;
return ;
}
int mid=(l+r)/; int lc=root*,rc=lc+;
if(ql<=mid) update(lc,l,mid); if(qr>mid) update(rc,mid+,r);
jump[root].sum=jump[lc].sum+jump[rc].sum;
} inline void query(int root,int l,int r){
pushdown(root);
if(ql<=l && r<=qr) {
daan+=jump[root].sum;
if(daan>=MOD) daan=daan%MOD;
return ;
}
int mid=(l+r)/; int lc=root*,rc=lc+;
if(ql<=mid) query(lc,l,mid); if(qr>mid) query(rc,mid+,r);
jump[root].sum=jump[lc].sum+jump[rc].sum;
} inline void lca(int x){
int f1=top[x];
while(x) {
ql=id[f1],qr=id[x];
update(,,n);
x=father[f1]; f1=top[x];
}
} inline int up(int x){
int f1=top[x];
int total=;
while(x) {
ql=id[f1]; qr=id[x]; daan=;
query(,,n);
total+=daan;
x=father[f1]; f1=top[x];
if(total>=MOD) total%=MOD;
}
return total;
} inline void build(int root,int l,int r){
jump[root].l=l; jump[root].r=r; jump[root].size=r-l+;
if(l==r) return ;
int mid=(l+r)/; int lc=root*,rc=lc+;
build(lc,l,mid); build(rc,mid+,r);
} inline void work(){
n=getint(); q=getint();
for(int i=;i<n;i++) {
father[i+]=getint()+;
next[++ecnt]=first[father[i+]]; to[ecnt]=i+; first[father[i+]]=ecnt;
}
deep[]=; dfs(,); top[]=; ecnt=; dfs2(,);
int x,y,z;
ecnt=;
for(int i=;i<=q;i++) {
x=getint()+; y=getint()+; z=getint()+;
a[++ecnt].pos=x-; a[ecnt].id=ecnt; a[ecnt].z=z;
a[++ecnt].pos=y; a[ecnt].id=ecnt; a[ecnt].z=z;
}
sort(a+,a+ecnt+,cmp);
int now=;
build(,,n);
for(int i=;i<=ecnt;i++) {
while(now<a[i].pos) {
lca(now+); now++;
}
a[i].ans=up(a[i].z); if(a[i].ans>MOD) a[i].ans%=MOD;
} sort(a+,a+ecnt+,ccmp);
for(int i=;i<=ecnt;i+=) printf("%d\n",( (a[i+].ans-a[i].ans)+MOD )%MOD);
} int main()
{
work();
return ;
}