题意

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

前言

这题是我自己想的哈。。感觉和网上的方法都不一样啊
感觉十分开心啊。。
在这里提供一下的做法吧

题解

首先，为了方便
我将询问变成了两个，一个值正贡献1~r,一个是负贡献1~l-1
那么对于端点一样的一起做就可以了
分来做两次就可以了
考虑怎么求答案
我是怎么想的呢？
我可以让z不断往上跳
如果从x跳到了xx
那么这个的贡献就是xx除了x的子树里，有多少个点在所求范围内
这个显然是可以树剖的
我们考虑每一个节点只维护他的轻儿子还有他自己的两个信息
一个是有多少个$c_0$,一个是$c_0*dep$,记为$c1$
维护好这两个东西以后
就跳重链就可以了
如果是一条重链，那么就是$c1$的总和了
因为要踢掉的正好是重儿子
对于跨过一条轻链，我们就暴力算一下他的贡献就可以了
这个时候求出求出除了这个儿子以为还有多少个节点存在
然后就可以了

CODE:

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
typedef long long LL;
const LL MOD=201314;
const LL N=50005;
LL n,q;
struct qq {LL l,r,x,id; }s[N];
struct qt
{LL x,y,last;
}e[N];LL num,last[N];
struct qy
{LL l,r;LL s1,s2;LL c[2];
}tr[N*2];
LL ans[N];
bool cmp (qq x,qq y){
   return x.r<y.r;}
bool cmp1 (qq x,qq y){
   return x.l<y.l;}
void init (LL x,LL y)
{num++;e[num].x=x;e[num].y=y;e[num].last=last[x];last[x]=num;
}
LL tot[N],son[N],fa[N],top[N];
LL L[N],R[N];
LL belong[N];
LL dep[N];
void bt (LL l,LL r)
{LL a=++num;tr[a].l=l;tr[a].r=r;if (l==r)return ;LL mid=(l+r)>>1;tr[a].s1=num+1;bt(l,mid);tr[a].s2=num+1;bt(mid+1,r);
}
void dfs (LL x)
{tot[x]=1;for (LL u=last[x];u!=-1;u=e[u].last){LL y=e[u].y;dep[y]=dep[x]+1;dfs(y);tot[x]=tot[x]+tot[y];if (tot[son[x]]<tot[y]) son[x]=y;}
}
void dfs1 (LL x,LL tp)
{top[x]=tp;L[x]=++num;belong[num]=x;if (son[x]!=0) dfs1(son[x],tp);for (LL u=last[x];u!=-1;u=e[u].last){LL y=e[u].y;if (y==son[x]) continue;dfs1(y,y);}R[x]=num;
}
void update (LL now)
{LL s1=tr[now].s1,s2=tr[now].s2;tr[now].c[0]=tr[s1].c[0]+tr[s2].c[0];tr[now].c[1]=tr[s1].c[1]+tr[s2].c[1];
}
void change (LL now,LL x,LL o)
{if (tr[now].l==tr[now].r){if (o==0) tr[now].c[0]++;else tr[now].c[1]=tr[now].c[1]+dep[belong[x]];return ;}LL mid=(tr[now].l+tr[now].r)>>1;LL s1=tr[now].s1,s2=tr[now].s2;if (x<=mid) change(s1,x,o);else change(s2,x,o);update(now);
}
void Add (LL x)//加入这个点 
{
//  printf("add:%lld\n",x);change(1,L[x],0);change(1,L[x],1);LL tx=top[x];while (tx!=1){LL ff=fa[tx];//  printf("YES:%lld\n",L[ff]);change(1,L[ff],1);x=ff;tx=top[x];}
}
LL get (LL now,LL l,LL r,LL o)
{if (l>r) return 0;if (tr[now].l==l&&tr[now].r==r)   return tr[now].c[o];LL mid=(tr[now].l+tr[now].r)>>1;LL s1=tr[now].s1,s2=tr[now].s2;if (r<=mid) return get(s1,l,r,o);else if (l>mid) return get(s2,l,r,o);else return get(s1,l,mid,o)+get(s2,mid+1,r,o);
}
LL get (LL x)//得到这个点的答案 
{//printf("find:%lld\n",x);LL lalal=0;lalal=lalal+get(1,L[x],R[x],0)*dep[x];
//  printf("p:%lld\n",lalal);LL tx=top[x];while (x!=0){LL ff=fa[tx];lalal=lalal+get(1,L[tx],L[x]-1,1);if (ff!=0) lalal=lalal+(get(1,L[ff],R[ff],0)-get(1,L[tx],R[tx],0))*dep[ff]; 
//      printf("%lld %lld %lld %lld %lld\n",tx,x,lalal,L[tx],L[x]-1);x=fa[tx];tx=top[x];}return lalal;
}
void solve ()
{sort(s+1,s+1+q,cmp);LL now=1;//现在增加到第几个点 for (LL u=1;u<=q;u++){while (now<=s[u].r)  Add(now++);ans[s[u].id]+=get(s[u].x);}for (LL u=1;u<=num;u++) tr[u].c[0]=tr[u].c[1]=0;sort(s+1,s+1+q,cmp1);now=1;for (LL u=1;u<=q;u++){while (now<s[u].l)   Add(now++);ans[s[u].id]-=get(s[u].x);}
}
int main()
{num=0;memset(last,-1,sizeof(last));scanf("%lld%lld",&n,&q);for (LL u=2;u<=n;u++){LL x;scanf("%lld",&x);x++;fa[u]=x;init(x,u);}dep[1]=1;num=0;dfs(1);dfs1(1,1);
//  for (LL u=1;u<=n;u++) printf("%lld %lld %lld\n",dep[u],son[u],L[u]);num=0;bt(1,n);for (LL u=1;u<=q;u++){scanf("%lld%lld%lld",&s[u].l,&s[u].r,&s[u].x);s[u].l++;s[u].r++;s[u].x++;s[u].id=u;}solve();for (LL u=1;u<=q;u++)    printf("%lld\n",ans[u]%MOD);return 0;
}
?