题目：https://www.lydsy.com/JudgeOnline/problem.php?id=3626
竟然是这样看。
深度可以差分表示。一个点的深度计入贡献可以表示成给它到根的链上所有点的值+1。LCA的深度就变成对方到根节点的链上的值。
l~r与z的LCA的深度和 就是把 l~r 都这样做一遍，然后求z到根的链上的值。
然后就变成树链剖分模板。
这里要对每个 l 和 r 排序，枚举计入贡献的点从1到n，达到一个前缀的效果（1~r - 1~(l-1)）。
因为z各有不同，所以最好一遇到某个询问的 l 或 r 就算一下。不然岂不是要记录所有 z 对应的前缀和？
注意的一点是init里的那个地方。要先调一调。
（不知为何自己的代码比别人慢！仔细一想不会爆long long所以把中间的取模去掉，还是那么慢！）
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; const int N=5e4+5;const ll mod=201314; int n,m,head[N],tot,dl,dr; int fa[N],son[N],siz[N],rnk[N],top[N]; struct Node{int ls,rs;ll val,laz,cd; }a[N<<1]; struct Ques{int l,r,z;ll ansl,ansr; }q[N]; struct Edge{int next,to; }edge[N]; struct Tmp{int v,id; }tl[N],tr[N]; bool cmp(Tmp a,Tmp b){return a.v<b.v;} int rdn() {int ret=0;char ch=getchar();while(ch>'9'||ch<'0')ch=getchar();while(ch>='0'&&ch<='9')(ret*=10)+=ch-'0',ch=getchar();return ret; } void dfs1(int cr) {siz[cr]=1;for(int i=head[cr],v;i;i=edge[i].next)if((v=edge[i].to)!=fa[cr]){dfs1(v);siz[cr]+=siz[v];if(siz[v]>siz[son[cr]])son[cr]=v;} } void dfs2(int cr) {rnk[cr]=++tot;if(!son[cr])return;top[son[cr]]=top[cr];dfs2(son[cr]);for(int i=head[cr],v;i;i=edge[i].next)if((v=edge[i].to)!=fa[cr]&&v!=son[cr]){top[v]=v;dfs2(v);} } void build(int l,int r,int cr) {if(l==r){a[cr].cd=1;return;}a[cr].cd=r-l+1;int mid=((l+r)>>1);a[cr].ls=++tot;build(l,mid,tot);a[cr].rs=++tot;build(mid+1,r,tot); } void init() {dfs1(1);top[1]=1;dfs2(1);tot=1;build(1,n,1);for(dl=1;dl<=m&&tl[dl].v<=1;dl++);for(dr=1;dr<=m&&!tr[dr].v;dr++);// } void pushdown(int cr) {int ls=a[cr].ls,rs=a[cr].rs;ll laz=a[cr].laz;a[cr].laz=0;a[ls].laz+=laz;a[rs].laz+=laz;a[ls].val+=a[ls].cd*laz;a[rs].val+=a[rs].cd*laz; } void pushup(int cr) {a[cr].val=a[a[cr].ls].val+a[a[cr].rs].val; } void pls(int l,int r,int cr,int L,int R) {if(l>=L&&r<=R){a[cr].val+=a[cr].cd;a[cr].laz++;return;}pushdown(cr);int mid=((l+r)>>1);if(mid>=L)pls(l,mid,a[cr].ls,L,R);if(mid<R)pls(mid+1,r,a[cr].rs,L,R);pushup(cr); } ll qry(int l,int r,int cr,int L,int R) {if(l>=L&&r<=R)return a[cr].val;pushdown(cr);int mid=((l+r)>>1);ll ret=0;if(mid>=L)ret+=qry(l,mid,a[cr].ls,L,R);if(mid<R)ret+=qry(mid+1,r,a[cr].rs,L,R);pushup(cr);return ret; } void add(int k) {while(k){pls(1,n,1,rnk[top[k]],rnk[k]);k=fa[top[k]];} } ll query(int k) {ll ret=0;while(k){ret+=qry(1,n,1,rnk[top[k]],rnk[k]);k=fa[top[k]];}return ret; } int main() {n=rdn();m=rdn();for(int i=2;i<=n;i++){fa[i]=rdn()+1;edge[i].next=head[fa[i]];edge[i].to=i;head[fa[i]]=i;}for(int i=1;i<=m;i++){tl[i].v=q[i].l=rdn()+1;tr[i].v=q[i].r=rdn()+1;q[i].z=rdn()+1;tl[i].id=i;tr[i].id=i;}sort(tl+1,tl+m+1,cmp);sort(tr+1,tr+m+1,cmp);init();for(int i=1;i<=n;i++){add(i);while(dl<=m&&tl[dl].v-1==i)q[tl[dl].id].ansl=query(q[tl[dl++].id].z);while(dr<=m&&tr[dr].v==i)q[tr[dr].id].ansr=query(q[tr[dr++].id].z);}for(int i=1;i<=m;i++)printf("%lld\n",(q[i].ansr-q[i].ansl)%mod);// return 0; }