给出一个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的最近公共祖先的深度之和）

第一行2个整数n q。
接下来n-1行，分别表示点1到点n-1的父节点编号。
接下来q行，每行3个整数l r z。

输出q行，每行表示一个询问的答案。每个答案对201314取模输出

共5组数据，n与q的规模分别为10000,20000,30000,40000,50000。

#include<cstdio>#include<iostream>#include<cstring>#include<cstdlib>#include<algorithm>#include<cmath>#include<deque>#include<set>#include<map>#include<ctime>#define LL long long#define inf 0x7ffffff#define pa pair<int,int>#define pi 3.1415926535897932384626433832795028841971#define N 100010#define mod 201314using namespace std;inline LL read(){    LL 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*10+ch-‘0‘;ch=getchar();}    return x*f;}int n,m,cnt,cnt2,tt,now=1;struct edge{int to,next;}e[2*N];struct segtree{int l,r,sum,tag;}tree[4*N];struct query{int lim,lca,rnk,res;}q[200010];inline bool cmp(const query &a,const query &b){return a.lim<b.lim;}int head[N];int mrk[N],son[N],depth[N],fa[N][21];int place[N],pplace[N],belong[N];int qrnk[100010];inline void ins(int u,int v){	e[++cnt].to=v;	e[cnt].next=head[u];	head[u]=cnt;}inline void insert(int u,int v){	ins(u,v);	ins(v,u);}inline void dfs1(int x,int dep){	if (mrk[x])return;	mrk[x]=1;son[x]=1;depth[x]=dep;	for (int i=1;i<=20;i++)	  fa[x][i]=fa[fa[x][i-1]][i-1];	for (int i=head[x];i;i=e[i].next)	  	if (!mrk[e[i].to])		{			dfs1(e[i].to,dep+1);			son[x]+=son[e[i].to];		}}inline void dfs2(int x,int chain){	place[x]=++tt;pplace[tt]=x;	belong[x]=chain;	int mx=-1,res=-1;	for (int i=head[x];i;i=e[i].next)	  if (e[i].to!=fa[x][0])	  {	  	if (son[e[i].to]>mx)	  	{	  		mx=son[e[i].to];	  		res=e[i].to;	  	}	  }	if (res==-1)return;	dfs2(res,chain);	for (int i=head[x];i;i=e[i].next)	if (e[i].to!=res&&e[i].to!=fa[x][0])	    dfs2(e[i].to,e[i].to);}inline int LCA(int a,int b){	if (depth[a]<depth[b])swap(a,b);	int res=depth[a]-depth[b];	for (int i=0;i<=20;i++)	  if (res & (1<<i))a=fa[a][i];	for (int i=20;i>=0;i--)	  if (fa[a][i]!=fa[b][i])	  {	  	a=fa[a][i];	  	b=fa[b][i];	  }	if (a==b)return a;	return fa[a][0];}inline void update(int k){	tree[k].sum=tree[k<<1].sum+tree[k<<1|1].sum;}inline void pushdown(int k){	int tag=tree[k].tag;tree[k].tag=-1;	if (tag==-1||tree[k].l==tree[k].r)return; 	tree[k<<1].sum+=(tree[k<<1].r-tree[k<<1].l+1)*tag;	tree[k<<1|1].sum+=(tree[k<<1|1].r-tree[k<<1|1].l+1)*tag;	if (tree[k<<1].tag==-1)tree[k<<1].tag=tag;	else tree[k<<1].tag+=tag;	if (tree[k<<1|1].tag==-1)tree[k<<1|1].tag=tag;	else tree[k<<1|1].tag+=tag;}inline void buildtree(int now,int l,int r){	tree[now].l=l;tree[now].r=r;tree[now].tag=-1;	if (l==r)return;	int mid=(l+r)>>1;	buildtree(now<<1,l,mid);	buildtree(now<<1|1,mid+1,r);}inline void add_in_tree(int now,int x,int y,int dat){	pushdown(now);	int l=tree[now].l,r=tree[now].r;	if (l==x&&r==y)	{		tree[now].sum+=(r-l+1)*dat;		tree[now].tag=dat;		return;	}	int mid=(l+r)>>1;	if (y<=mid) add_in_tree(now<<1,x,y,dat);	else if (x>mid) add_in_tree(now<<1|1,x,y,dat);	else	{		add_in_tree(now<<1,x,mid,dat);		add_in_tree(now<<1|1,mid+1,y,dat);	}	update(now);}inline int ask_in_tree(int now,int x,int y){	pushdown(now);	int l=tree[now].l,r=tree[now].r;	if (l==x&&r==y)return tree[now].sum;	int mid=(l+r)>>1;	if (y<=mid)return ask_in_tree(now<<1,x,y);	else if(x>mid)return ask_in_tree(now<<1|1,x,y);	else return ask_in_tree(now<<1,x,mid)+ask_in_tree(now<<1|1,mid+1,y);}inline void add(int from,int to,int dat){	int l,r;	while (belong[from]!=belong[to])	{		l=place[belong[from]];		r=place[from];		add_in_tree(1,l,r,dat);		from=fa[belong[from]][0];	}	l=place[to];	r=place[from];	add_in_tree(1,l,r,dat);}inline int ask(int from,int to){	int l,r,s=0;	while (belong[from]!=belong[to])	{		l=place[belong[from]];		r=place[from];		s=(ask_in_tree(1,l,r)+s)%mod;		from=fa[belong[from]][0];	}	l=place[to];	r=place[from];	s=(s+ask_in_tree(1,l,r))%mod;	return s;}int main(){	n=read();m=read();	for (int i=2;i<=n;i++)	{		fa[i][0]=read()+1;		insert(fa[i][0],i);	}	dfs1(1,1);	dfs2(1,1);	buildtree(1,1,n);	for (int i=1;i<=m;i++)	{		int x=read()+1,y=read()+1,z=read()+1;		q[++cnt2].lim=x-1;q[cnt2].lca=z;q[cnt2].rnk=cnt2;		q[++cnt2].lim=y;q[cnt2].lca=z;q[cnt2].rnk=cnt2;	}	sort(q+1,q+2*m+1,cmp);	while (q[now].lim==0)now++;	for(int i=1;i<=n;i++)	{		add(i,1,1);		while(q[now].lim==i&&now<=2*m)		{			  q[now].res=ask(q[now].lca,1);			  now++;		}	}	for (int i=1;i<=2*m;i++)qrnk[q[i].rnk]=q[i].res;	for (int i=1;i<=m;i++)	  printf("%d\n",(qrnk[2*i]-qrnk[2*i-1]+mod)%mod);}