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
5 2
0
0
1
1
1 4 3
1 4 2
0
0
1
1
1 4 3
1 4 2
Sample Output
8
5
5
HINT
共5组数据，n与q的规模分别为10000,20000,30000,40000,50000。
Source
数据已加强 by saffah
~~~~~~~~~~~~~~~~~~~~~~~~~~~~
树链剖分～
对于每个询问l，r，v，相当于将v到根节点的路径上的点权值+1，然后任意i属于[l,r]，求到根节点的路径的权值和。
然后求这个又相当于是对于i属于[l,r]的每个i，到根节点的路径都+1，然后求v到根节点的路径的权值和。
所以我们将询问离线，每个询问可以表示为ans(1,r)-ans(1,l-1)，把每个询问分为添加和减去的两个操作，按照操作位置（即l和r-1）排序，每次添加后查询即可。这里还用到了差分。
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define modd 201314int n,m,x,y,z,fi[50001],w[50001],ne[50001],cnt,fa[50001],son[50001],siz[50001],dep[50001],top[50001],id[50001],now;struct node{int l,r,num,siz,tag;
}a[50001<<2];struct node1{int id,x;bool flag;
}q[50001<<1];struct node2{int a1,a2,x;
}ans[50001];bool operator < (node1 u,node1 v)
{return u.x<v.x;
}int read()
{int x=0,f=1;char ch=getchar();while(ch<'0' || ch>'9') {if(ch=='-') f=-1;ch=getchar();}while(ch>='0' && ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;
}void add(int u,int v)
{w[++cnt]=v;ne[cnt]=fi[u];fi[u]=cnt;fa[v]=u;
}void dfs1(int u)
{siz[u]=1;son[u]=0;for(int i=fi[u];i;i=ne[i]){dep[w[i]]=dep[u]+1;dfs1(w[i]);siz[u]+=siz[w[i]];if(!son[u] || siz[son[u]]<siz[w[i]]) son[u]=w[i];}
}void dfs2(int u,int la)
{top[u]=la;id[u]=++cnt;if(son[u]) dfs2(son[u],la);for(int i=fi[u];i;i=ne[i])if(w[i]!=son[u]) dfs2(w[i],w[i]);
}void build(int l,int r,int k)
{a[k].l=l;a[k].r=r;a[k].siz=r-l+1;if(l==r) return;int mid=l+r>>1;build(l,mid,k<<1);build(mid+1,r,k<<1|1);
}void pushdown(int k)
{if(a[k].l==a[k].r || !a[k].tag) return;int l=k<<1,r=k<<1|1,val=a[k].tag;a[k].tag=0;a[l].tag+=val;a[r].tag+=val;a[l].num+=a[l].siz*val;a[l].num%=modd;a[r].num+=a[r].siz*val;a[r].num%=modd;
}void chan(int k,int u,int v)
{pushdown(k);int l=a[k].l,r=a[k].r,mid=l+r>>1;if(l>=u && r<=v){a[k].num+=a[k].siz;a[k].tag++;return;}if(mid>=u) chan(k<<1,u,v);if(mid<v) chan(k<<1|1,u,v);a[k].num=a[k<<1].num+a[k<<1|1].num;
}int cal(int k,int u,int v)
{pushdown(k);int l=a[k].l,r=a[k].r,mid=l+r>>1,now=0;if(u<=l && v>=r) return a[k].num;if(u<=mid) now+=cal(k<<1,u,v);if(v>mid) now+=cal(k<<1|1,u,v);return now%modd;
}void add_chan(int u,int v)
{while(top[u]!=top[v]){chan(1,id[top[u]],id[u]);u=fa[top[u]];}chan(1,id[v],id[u]);
}int query(int u,int v)
{int sum=0;while(top[u]!=top[v]){sum=(sum+cal(1,id[top[u]],id[u]))%modd;u=fa[top[u]];}return (sum+cal(1,id[v],id[u]))%modd;
}int main()
{n=read();m=read();for(int i=2;i<=n;i++) x=read(),add(x+1,i);dep[1]=1;cnt=0;dfs1(1);dfs2(1,1);build(1,n,1);cnt=0;for(int i=1;i<=m;i++){x=read()+1;y=read()+1;ans[i].x=read()+1;q[++cnt].id=i;q[cnt].x=x-1;q[cnt].flag=0;q[++cnt].id=i;q[cnt].x=y;q[cnt].flag=1;}sort(q+1,q+cnt+1);for(int i=1;i<=cnt;i++){while(now<q[i].x) add_chan(++now,1);int k=q[i].id;(q[i].flag ? ans[k].a2:ans[k].a1)=query(ans[k].x,1);}for(int i=1;i<=m;i++) printf("%d\n",(ans[i].a2-ans[i].a1+modd)%modd);return 0;
}