[LNOI2014]LCA
给出一个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的最近公共祖先的深度之和）
这道题一上来乍眼一看没什么思路，其实之后的每步都是套路；
对于LCA，我们首先会想到差分，没错，就是差分；
咋查分啊？一个区间的点啊,这复杂度可不是闹着玩的；
但有没有注意到，z只有一个；我们是否可以把整个区间在树上差分，然后用这一个点z来查询；
答案是当然可以：(注意：这里的差分与普通的树形差分不一样)
我们把z到root这条路上的所有点都打上标记(点的权值加1)；那么你会发现，这条路径上任意一点的深度就是到根节点的点权和；
所以询问区间[L,R],我们只要询问每个点到根节点的点权和就可以了；
另外，这个结论存在一个优美的性质：若将这个区间的所有点到根节点路径的点权值加1，那么询问时可以找z到根节点的权值和；
通过以上的的操作，我们将闹着玩的复杂度降到了似乎可做的复杂度;
接下来我们接着优化：
这么多区间的查询，是否想到了数位dp的经典处理方法？
没错，这是一个前缀和优化处理；
我们将询问离线掉；然后从1到n加入这个点；并将这个点到根节点的路径上所有点的权值加1；
然后复杂度变成了看起来好好做的样子；
在思维想不动的时候，就换种解题思路，使用数据结构大力维护每个点到根节点的点权和；
你想到了什么？树剖？LCT？没问题！
接下来就是愉快的AC时间了；
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define ll long long
#define inf 1000000000
#define mod 201314
using 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,place;
int bin[20];
int son[50005],last[50005],fa[50005],belong[50005],pl[50005],deep[50005];
struct edge{int to,next;}e[50005];
struct que{int z,ans1,ans2;}q[50005];
struct data{int num,p;bool flag;}a[100005];
struct seg{int l,r,sum,tag,size;}t[200005];
inline bool operator<(data a,data b)
{
return a.p<b.p;
}
inline void insert(int u,int v)
{
e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;
}
void dfs1(int x)
{
son[x]=1;
for(int i=last[x];i;i=e[i].next)
{
if(e[i].to==fa[x])continue;
deep[e[i].to]=deep[x]+1;
fa[e[i].to]=x;
dfs1(e[i].to);
son[x]+=son[e[i].to];
}
}
void dfs2(int x,int chain)
{
belong[x]=chain;pl[x]=++place;
int k=n;
for(int i=last[x];i;i=e[i].next)
if(e[i].to!=fa[x]&&son[e[i].to]>son[k])
k=e[i].to;
if(k!=n)dfs2(k,chain);
for(int i=last[x];i;i=e[i].next)
if(e[i].to!=fa[x]&&e[i].to!=k)
dfs2(e[i].to,e[i].to);
}
inline void pushdown(int k)
{
if(t[k].l==t[k].r||!t[k].tag)return;
int tag=t[k].tag;t[k].tag=0;
t[k<<1].sum=t[k<<1].sum+t[k<<1].size*tag;
t[k<<1|1].sum=t[k<<1|1].sum+t[k<<1|1].size*tag;
t[k<<1].tag=t[k<<1].tag+tag;
t[k<<1|1].tag=t[k<<1|1].tag+tag;
}
void build(int k,int l,int r)
{
t[k].l=l;t[k].r=r;t[k].size=r-l+1;
if(l==r)return;
int mid=(l+r)>>1;
build(k<<1,l,mid);
build(k<<1|1,mid+1,r);
}
void update(int k,int x,int y)
{
pushdown(k);
int l=t[k].l,r=t[k].r;
if(l==x&&y==r)
{
t[k].tag++;t[k].sum+=t[k].size;
return;
}
int mid=(l+r)>>1;
if(y<=mid)update(k<<1,x,y);
else if(x>mid)update(k<<1|1,x,y);
else
{
update(k<<1,x,mid);
update(k<<1|1,mid+1,y);
}
t[k].sum=t[k<<1].sum+t[k<<1|1].sum;
}
void solve_update(int x,int f)
{
while(belong[x]!=belong[f])
{
update(1,pl[belong[x]],pl[x]);
x=fa[belong[x]];
}
update(1,pl[f],pl[x]);
}
int query(int k,int x,int y)
{
pushdown(k);
int l=t[k].l,r=t[k].r;
if(l==x&&y==r)return t[k].sum;
int mid=(l+r)>>1;
if(y<=mid)return query(k<<1,x,y);
else if(x>mid)return query(k<<1|1,x,y);
else return query(k<<1,x,mid)+query(k<<1|1,mid+1,y);
}
int solve_query(int x,int f)
{
int sum=0;
while(belong[x]!=belong[f])
{
sum+=query(1,pl[belong[x]],pl[x]);
sum%=mod;
x=fa[belong[x]];
}
sum+=query(1,pl[f],pl[x]);sum%=mod;
return sum;
}
int main()
{
//freopen("lca.in","r",stdin);
//freopen("lca.out","w",stdout);
bin[0]=1;for(int i=1;i<20;i++)bin[i]=(bin[i-1]<<1);
n=read();m=read();
for(int i=1;i<n;i++)
{
int x=read();insert(x,i);
}
int tot=0;
for(int i=1;i<=m;i++)
{
int l=read(),r=read();
q[i].z=read();
a[++tot].p=l-1;a[tot].num=i;a[tot].flag=0;
a[++tot].p=r;a[tot].num=i;a[tot].flag=1;
}
build(1,1,n);
sort(a+1,a+tot+1);
dfs1(0);dfs2(0,0);
int now=-1;
for(int i=1;i<=tot;i++)
{
while(now<a[i].p)
{
now++;
solve_update(now,0);
}
int t=a[i].num;
if(!a[i].flag)q[t].ans1=solve_query(q[t].z,0);
else q[t].ans2=solve_query(q[t].z,0);
}
for(int i=1;i<=m;i++)
printf("%d\n",(q[i].ans2-q[i].ans1+mod)%mod);
return 0;
}