题目大意：给一棵树，q个询问，每次询问一个区间内的点与一个点的所有LCA的深度之和
很神的一道题啊...
首先对于每组询问，我们可以把这个区间内每个点到根的路径都+1，然后求被询问的点到根的路径和，就是这个询问的答案
然后我们可以把每组询问拆成两个，变成ans[R]-ans[L-1]
然后就可以离线，把0~n-1一个一个往里加，每次把它到根的路径+1，然后查询对应的那些询问就可以了
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 100010
using namespace std;
int to[N],nxt[N],pre[N],fa[N],cnt;
void ae(int ff,int tt)
{
cnt++;
to[cnt]=tt;
nxt[cnt]=pre[ff];
pre[ff]=cnt;
}
int d[N],zs[N],siz[N];
void build1(int x)
{
int maxn=0,maxb=0;
int i,j;
siz[x]=1;
for(i=pre[x];i;i=nxt[i])
{
j=to[i];
d[j]=d[x]+1;
fa[j]=x;
build1(j);
siz[x]+=siz[j];
if(siz[j]>maxn)
{
maxn=siz[j];
maxb=j;
}
}
zs[x]=maxb;
}
int top[N],sit[N],fan[N],cn;
void make(int x,int tt)
{
cn++;sit[x]=cn;fan[cn]=x;
top[x]=tt;
int i,j;
if(zs[x]) make(zs[x],tt);
for(i=pre[x];i;i=nxt[i])
{
j=to[i];
if(j==zs[x]) continue;
make(j,j);
}
}
struct ppp{int x,z,num,v;}b[N];
bool cmp(ppp x,ppp y){return x.x<y.x;}
int ans[N];
int l[N<<2],r[N<<2],sum[N<<2],t[N<<2];
void pup(int x){sum[x]=sum[x<<1]+sum[x<<1|1];}
void pud(int x)
{
sum[x<<1]+=(r[x<<1]-l[x<<1]+1)*t[x];
sum[x<<1|1]+=(r[x<<1|1]-l[x<<1|1]+1)*t[x];
t[x<<1]+=t[x];
t[x<<1|1]+=t[x];
t[x]=0;
}
void build(int now,int ll,int rr)
{
l[now]=ll;r[now]=rr;
if(ll==rr) return;
int mid=(ll+rr)>>1;
build(now<<1,ll,mid);
build(now<<1|1,mid+1,rr);
}
void change(int now,int ll,int rr)
{
if(l[now]==ll&&r[now]==rr)
{
t[now]++;
sum[now]+=r[now]-l[now]+1;
return;
}
if(t[now]) pud(now);
int mid=(l[now]+r[now])>>1;
if(rr<=mid) change(now<<1,ll,rr);
else if(ll>mid) change(now<<1|1,ll,rr);
else change(now<<1,ll,mid),change(now<<1|1,mid+1,rr);
pup(now);
}
int check(int now,int ll,int rr)
{
if(l[now]==ll&&r[now]==rr) return sum[now];
if(t[now]) pud(now);
int mid=(l[now]+r[now])>>1;
if(rr<=mid) return check(now<<1,ll,rr);
else if(ll>mid) return check(now<<1|1,ll,rr);
else return check(now<<1,ll,mid)+check(now<<1|1,mid+1,rr);
}
void changeit(int x)
{
while(x)
{
change(1,sit[top[x]],sit[x]);
x=fa[top[x]];
}
}
int checkit(int x)
{
int ans=0;
while(x)
{
ans+=check(1,sit[top[x]],sit[x]);
x=fa[top[x]];
}
return ans;
}
int mod=201314;
int main()
{
int n,q;
scanf("%d%d",&n,&q);
int i,j,x,y,z;
for(i=2;i<=n;i++)
{
scanf("%d",&x);
ae(x+1,i);
}
build1(1);
make(1,1);
for(i=1;i<=q;i++)
{
scanf("%d%d%d",&x,&y,&z);
x++;y++;z++;
b[2*i-1]=(ppp){x-1,z,i,-1};
b[2*i]=(ppp){y,z,i,1};
}
sort(b+1,b+2*q+1,cmp);
j=1;
while(b[j].x==0) j++;
build(1,1,n);
for(i=1;i<=n;i++)
{
changeit(i);
while(b[j].x==i)
{
ans[b[j].num]+=b[j].v*checkit(b[j].z);
j++;
}
}
for(i=1;i<=q;i++)
printf("%d\n",ans[i]%mod);
}