给出一个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。

思路：因为题目要求树上编号为[L,R]这段区间的节点和z的lca深度和，我们如果把1到z的这条路径上的点的值都标记为1，那么结果就是[L,R]中的点到根节点1的路径上的值的和，那么我们也可以反过来想，我们先把[L,R]区间内1到i的路径经过的点都加上1，那么答案就是[1,R]的结果减去[1,L-1]的结果，然后我们可以离线处理询问了。

#include<iostream>

#include<stdio.h>

#include<stdlib.h>

#include<string.h>

#include<math.h>

#include<vector>

#include<map>

#include<set>

#include<string>

#include<bitset>

#include<algorithm>

using namespace std;

#define lson th<<1

#define rson th<<1|1

typedef long long ll;

typedef long double ldb;

#define inf 99999999

#define pi acos(-1.0)

#define MOD 201314

#define maxn 50050

struct edge{

    int to,next;

}e[2*maxn];

int first[maxn],tot;

void addedge(int u,int v)

{

    tot++;

    e[tot].to=v;e[tot].next=first[u];

    first[u]=tot;

}

int son[maxn],num[maxn],fa[maxn],dep[maxn];

int p[maxn],top[maxn],pos;

void dfs1(int u,int pre)

{

    int i,j,v;

    dep[u]=dep[pre]+1;

    fa[u]=pre;

    num[u]=1;

    for(i=first[u];i!=-1;i=e[i].next){

        v=e[i].to;

        if(v==pre)continue;

        dfs1(v,u);

        if(son[u]==-1 || num[son[u] ]<num[v]){

            son[u]=v;

        }

        num[u]+=num[v];

    }

}

void dfs2(int u,int tp)

{

    int i,j,v;

    top[u]=tp;

    if(son[u]!=-1){

        p[u]=++pos;

        dfs2(son[u],tp);

    }

    else{

        p[u]=++pos;

        return;

    }

    for(i=first[u];i!=-1;i=e[i].next){

        v=e[i].to;

        if(v==fa[u] || v==son[u])continue;

        dfs2(v,v);

    }

}

//线段树部分

struct node{

    int l,r,add;

    ll sum;

}b[4*maxn];

void build(int l,int r,int th)

{

    int mid;

    b[th].l=l;b[th].r=r;

    b[th].add=b[th].sum=0;

    if(l==r)return;

    mid=(l+r)/2;

    build(l,mid,lson);

    build(mid+1,r,rson);

}

void pushdown(int th)

{

    if(b[th].add){

        b[lson].add+=b[th].add;

        b[lson].sum+=(ll)(b[lson].r-b[lson].l+1)*(ll)b[th].add;

        b[rson].add+=b[th].add;

        b[rson].sum+=(ll)(b[rson].r-b[rson].l+1)*(ll)b[th].add;

        b[th].add=0;

    }

}

void pushup(int th)

{

    b[th].sum=b[lson].sum+b[rson].sum;

}

void update(int l,int r,int add,int th)

{

    int mid;

    if(b[th].l==l && b[th].r==r){

        b[th].add+=add;

        b[th].sum+=(ll)(b[th].r-b[th].l+1)*(ll)add;

        return;

    }

    pushdown(th);

    mid=(b[th].l+b[th].r)/2;

    if(r<=mid)update(l,r,add,lson);

    else if(l>mid)update(l,r,add,rson);

    else{

        update(l,mid,add,lson);

        update(mid+1,r,add,rson);

    }

    pushup(th);

}

ll question(int l,int r,int th)

{

    int mid;

    if(b[th].l==l && b[th].r==r){

        return b[th].sum;

    }

    pushdown(th);

    mid=(b[th].l+b[th].r)/2;

    if(r<=mid)return question(l,r,lson);

    else if(l>mid)return question(l,r,rson);

    else{

        return question(l,mid,lson)+question(mid+1,r,rson);

    }

}

ll ans[maxn][2];

struct node1{

    int l,r,z;

}q[maxn];

vector<pair<pair<int,int>,int> >vec[maxn];   //z,idx

vector<pair<pair<int,int>,int> >::iterator it;

void gengxin(int u)

{

    int i,j;

    while(u!=0){

        update(p[top[u]],p[u],1,1);

        u=fa[top[u] ];

    }

}

ll xunwen(int u)

{

    int i,j;

    ll num=0;

    while(u!=0){

        num+=question(p[top[u]],p[u],1);

        u=fa[top[u] ];

    }

    return num;

}

int main()

{

    int n,m,i,j,c,f,z,idx;

    while(scanf("%d%d",&n,&m)!=EOF)

    {

        memset(first,-1,sizeof(first));

        memset(son,-1,sizeof(son));

        tot=0;

        pos=0;

        for(i=0;i<=n;i++)vec[i].clear();

        for(i=2;i<=n;i++){

            scanf("%d",&c);c++;

            addedge(i,c);

            addedge(c,i);

        }

        dep[0]=0;

        dfs1(1,0);

        dfs2(1,1);

        build(1,pos,1);

        for(i=1;i<=m;i++){

            scanf("%d%d%d",&q[i].l,&q[i].r,&q[i].z);

            q[i].l++;q[i].r++;q[i].z++;

            vec[q[i].l-1 ].push_back(make_pair(make_pair(q[i].z,i),0) );

            vec[q[i].r ].push_back(make_pair(make_pair(q[i].z,i),1) );

        }

        for(i=1;i<=n;i++){

            gengxin(i);

            for(j=0;j<vec[i].size();j++){

                f=vec[i][j].second;

                z=vec[i][j].first.first;

                idx=vec[i][j].first.second;

                ans[idx ][f]=xunwen(z);

            }

        }

        for(i=1;i<=m;i++){

            if(q[i].l==1)printf("%lld\n",ans[i][1]%MOD);

            else printf("%lld\n",(ans[i][1]-ans[i][0])%MOD );

        }

    }

    return 0;

}