题目：https://www.lydsy.com/JudgeOnline/problem.php?id=3626
思路很巧妙，把区间换成前缀和相减；
把 l ~ r 到根路径上的点的点权都+1，然后 z 到根求和，就是 z 与 l ~ r 每个点 lca 深度的和；
这里若要用前缀和，则需要把询问离线排序；
然后上树链剖分，修改和求和线段树解决即可。
代码如下：
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; typedef long long ll; int const maxn=50005,mod=201314; int n,m,fa[maxn],head[maxn],ct,dfn[maxn],tim; int top[maxn],to[maxn],siz[maxn],tl[maxn],tr[maxn]; struct N{ int to,next; N(int t=0,int n=0):to(t),next(n) {} }edge[maxn<<1]; struct T{ll s,lzy,size;}t[maxn<<2]; struct Q{int l,r,z,bh;ll ansl,ansr;}q[maxn]; void add(int x,int y){edge[++ct]=N(y,head[x]);head[x]=ct;} bool cmp(int x,int y){return q[x].l<q[y].l;} bool cmp2(int x,int y){return q[x].r<q[y].r;} int rd() { int ret=0;char ch=getchar(); while(ch<'0'||ch>'9')ch=getchar(); while(ch>='0'&&ch<='9')ret=ret*10+ch-'0',ch=getchar(); return ret; } void dfs(int x,int f) { siz[x]=1; for(int i=head[x];i;i=edge[i].next) { int u=edge[i].to; if(u==f)continue; dfs(u,x); siz[x]+=siz[u]; if(siz[u]>siz[to[x]])to[x]=u; } } void dfs2(int x) { dfn[x]=++tim; if(to[x])top[to[x]]=top[x],dfs2(to[x]); for(int i=head[x];i;i=edge[i].next) { int u=edge[i].to; if(u==fa[x]||u==to[x])continue; top[u]=u; //top[u]!=x !!! dfs2(u); } } void pushup(int x) { t[x].size=t[x<<1].size+t[x<<1|1].size; t[x].s=t[x<<1].s+t[x<<1|1].s; } void pushdown(int x) { if(!t[x].lzy)return; int ls=(x<<1),rs=(x<<1|1); ll l=t[x].lzy;t[x].lzy=0; t[ls].s+=l*t[ls].size; t[ls].lzy+=l; t[rs].s+=l*t[rs].size; t[rs].lzy+=l; } void build(int x,int l,int r) { if(l==r){t[x].size=1; return;} int mid=((l+r)>>1); build(x<<1,l,mid); build(x<<1|1,mid+1,r); pushup(x); } void update(int x,int l,int r,int L,int R) { if(l>=L&&r<=R) { t[x].s+=t[x].size; t[x].lzy++; return; } pushdown(x); int mid=((l+r)>>1); if(mid>=L)update(x<<1,l,mid,L,R); if(mid<R)update(x<<1|1,mid+1,r,L,R); pushup(x); } void work(int x)//x 到 rt 路径上点权+1 { while(x) { update(1,1,n,dfn[top[x]],dfn[x]); x=fa[top[x]]; } // update(1,1,n,dfn[rt],dfn[rt]); } ll query(int x,int l,int r,int L,int R) { if(l>=L&&r<=R)return t[x].s; int mid=((l+r)>>1); ll ret=0; pushdown(x); if(mid>=L)ret+=query(x<<1,l,mid,L,R); if(mid<R)ret+=query(x<<1|1,mid+1,r,L,R); return ret; } ll qry(int x) { ll ret=0; while(x) { ret+=query(1,1,n,dfn[top[x]],dfn[x]); x=fa[top[x]]; } return ret; } int main() { n=rd();m=rd(); for(int i=2;i<=n;i++){fa[i]=rd()+1; add(fa[i],i); add(i,fa[i]);} for(int i=1;i<=m;i++) { q[i].l=rd()+1; q[i].r=rd()+1; q[i].z=rd()+1; tl[i]=i; tr[i]=i; } sort(tl+1,tl+m+1,cmp); sort(tr+1,tr+m+1,cmp2); dfs(1,0); top[1]=1; dfs2(1); build(1,1,n); int dl=1,dr=1; while(q[tl[dl]].l==1)dl++; for(int i=1;i<=n;i++) { work(i); while(q[tl[dl]].l-1==i&&dl<=m) { q[tl[dl]].ansl=qry(q[tl[dl]].z);//不套 dfn !!! dl++; } while(q[tr[dr]].r==i&&dr<=m) { q[tr[dr]].ansr=qry(q[tr[dr]].z); dr++; } } for(int i=1;i<=m;i++) printf("%lld ",(q[i].ansr-q[i].ansl)%mod); return 0; }