[文章目录]
Description
给出一个n个节点的有根树（编号为0到n-1，根节点为0）。一个点的深度定义为这个节点到根的距离+1。设dep[i]表示点i的深度，LCA(i,j)表示i与j的最近公共祖先。有q次询问，每次询问给出l r z，求。（即，求在[l,r]区间内的每个节点i与z的最近公共祖先的深度之和）
对于一个dep[LCA(i,z)]，假使在i这个点到根节点的路径上每个点权值+1，那么它的值等同于z点到根节点的路径上所有点权的和。
那么就可以对询问离线，差分区间，排序。按照编号从小到大处理询问，链剖维护到根节点的路径上的点权修改和查询。时间复杂度O()
别忘了取模
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 51000
const int mod=201314;
int n,m;
int head[N],to[N],nxt[N],cnt;
inline void add(int x,int y)
{
to[++cnt]=y; nxt[cnt]=head[x]; head[x]=cnt;
}
int fa[N],tid[N],top[N],son[N],siz[N<<2],dep[N],tim;
void dfs1(int x)
{
siz[x]=1;
for(int i=head[x];i;i=nxt[i])
{
dep[to[i]]=dep[x]+1; fa[to[i]]=x;
dfs1(to[i]); siz[x]+=siz[to[i]];
if(!son[x]||siz[to[i]]>siz[son[x]]) son[x]=to[i];
}
}
void dfs2(int x,int anc)
{
tid[x]=++tim; top[x]=anc;
if(son[x]) dfs2(son[x],anc);
for(int i=head[x];i;i=nxt[i]) if(to[i]!=son[x])
dfs2(to[i],to[i]);
}
int ans[N];
struct node
{
int id,fl,r,w;
}a[N<<1];
bool cmp(node x,node y){return x.r<y.r;}
int sum[N<<2],lz[N<<2];
void build(int pos,int l,int r)
{
siz[pos]=r-l+1;
if(l==r) return ;
int mid=(l+r)>>1;
build(pos<<1,l,mid);
build(pos<<1|1,mid+1,r);
}
inline void pushup(int pos) {sum[pos]=sum[pos<<1]+sum[pos<<1|1];}
inline void pushdown(int pos)
{
if(lz[pos])
{
sum[pos<<1]+=siz[pos<<1]*lz[pos];
sum[pos<<1|1]+=siz[pos<<1|1]*lz[pos];
lz[pos<<1]+=lz[pos]; lz[pos<<1|1]+=lz[pos];
lz[pos]=0;
}
}
void fix(int pos,int l,int r,int x,int y)
{
if(x<=l&&y>=r)
{
sum[pos]+=siz[pos]; lz[pos]++;
return ;
}
int mid=(l+r)>>1; pushdown(pos);
if(y<=mid) fix(pos<<1,l,mid,x,y);
else if(x>mid) fix(pos<<1|1,mid+1,r,x,y);
else fix(pos<<1,l,mid,x,y),fix(pos<<1|1,mid+1,r,x,y);
pushup(pos);
}
int query(int pos,int l,int r,int x,int y)
{
if(x<=l&&y>=r) return sum[pos];
int mid=(l+r)>>1; pushdown(pos);
if(y<=mid) return query(pos<<1,l,mid,x,y);
else if(x>mid) return query(pos<<1|1,mid+1,r,x,y);
else return query(pos<<1,l,mid,x,y)+query(pos<<1|1,mid+1,r,x,y);
}
inline void Fix(int x)
{
while(top[x])
{
fix(1,1,n,tid[top[x]],tid[x]);
x=fa[top[x]];
}
fix(1,1,n,1,tid[x]);
}
inline int Query(int x)
{
int re=0;
while(top[x])
{
re+=query(1,1,n,tid[top[x]],tid[x]);
x=fa[top[x]];
}
return re+query(1,1,n,1,tid[x]);
}
int main()
{
scanf("%d%d",&n,&m);
int x;
for(int i=1;i<n;++i)
{
scanf("%d",&x);
add(x,i);
}
dfs1(0); dfs2(0,0); build(1,1,n);
int l,r,z;
for(int i=1;i<=m;++i)
{
scanf("%d%d%d",&l,&r,&z);
a[i].id=i; a[i].fl=-1; a[i].r=l-1; a[i].w=z;
a[i+m].id=i; a[i+m].fl=1; a[i+m].r=r; a[i+m].w=z;
}
m<<=1; sort(a+1,a+m+1,cmp); int now=-1;
for(int i=1;i<=m;++i)
{
while(now<a[i].r) Fix(++now);
ans[a[i].id]+=a[i].fl*Query(a[i].w);
}
m>>=1;
for(int i=1;i<=m;++i) printf("%d\n",ans[i]%mod);
return 0;
}