欢迎访问~原文出处——博客园-zhouzhendong
去博客园看该题解
题目传送门 - BZOJ3626
题意概括
给出一个n个节点的有根树（编号为0到n-1，根节点为0）。一个点的深度定义为这个节点到根的距离+1。
设dep[i]表示点i的深度，LCA(i,j)表示i与j的最近公共祖先。
有q次询问，每次询问给出l r z，求在[l,r]区间内的每个节点i与z的最近公共祖先的深度之和
题解
代码
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <vector>
using namespace std;
const int N=50005,mod=201314;
struct Gragh{
int cnt,y[N*2],nxt[N*2],fst[N];
void clear(){
cnt=0;
memset(fst,0,sizeof fst);
}
void add(int a,int b){
y[++cnt]=b,nxt[cnt]=fst[a],fst[a]=cnt;
}
}g;
int n,q,cnp=0,ans[N],L[N],R[N],wn[N];
int fa[N],son[N],depth[N],size[N],top[N],p[N],ap[N];
vector <int> bh[N];
struct Tree{
int v,add,size;
}t[N*4];
void Get_Gen_Info(int rt,int pre,int d){
depth[rt]=d,fa[rt]=pre,size[rt]=1,son[rt]=-1;
for (int i=g.fst[rt];i;i=g.nxt[i])
if (g.y[i]!=pre){
int s=g.y[i];
Get_Gen_Info(s,rt,d+1);
size[rt]+=size[s];
if (son[rt]==-1||size[s]>size[son[rt]])
son[rt]=s;
}
}
void Get_Top(int rt,int tp){
top[rt]=tp;
ap[p[rt]=++cnp]=rt;
if (son[rt]==-1)
return;
Get_Top(son[rt],tp);
for (int i=g.fst[rt];i;i=g.nxt[i]){
int s=g.y[i];
if (s!=fa[rt]&&s!=son[rt])
Get_Top(s,s);
}
}
void pushup(int rt){
int ls=rt<<1,rs=ls|1;
t[rt].v=t[ls].v+t[rs].v;
}
void build(int rt,int le,int ri){
t[rt].add=t[rt].v=0,t[rt].size=ri-le+1;
if (le==ri)
return;
int mid=(le+ri)>>1,ls=rt<<1,rs=ls|1;
build(ls,le,mid);
build(rs,mid+1,ri);
}
void pushdown(int rt){
int ls=rt<<1,rs=ls|1,&a=t[rt].add;
if (a){
t[ls].add+=a,t[ls].v+=a*t[ls].size;
t[rs].add+=a,t[rs].v+=a*t[rs].size;
a=0;
}
}
void update(int rt,int le,int ri,int xle,int xri,int v){
if (xle>ri||xri<le)
return;
if (xle<=le&&ri<=xri){
t[rt].v+=v*t[rt].size;
t[rt].add+=v;
return;
}
pushdown(rt);
int mid=(le+ri)>>1,ls=rt<<1,rs=ls|1;
update(ls,le,mid,xle,xri,v);
update(rs,mid+1,ri,xle,xri,v);
pushup(rt);
}
int query(int rt,int le,int ri,int xle,int xri){
if (xle>ri||xri<le)
return 0;
if (xle<=le&&ri<=xri)
return t[rt].v;
pushdown(rt);
int mid=(le+ri)>>1,ls=rt<<1,rs=ls|1;
return query(ls,le,mid,xle,xri)+query(rs,mid+1,ri,xle,xri);
}
void Tupdate(int a){
int f=top[a];
while (a){
update(1,1,n,p[f],p[a],1);
a=fa[f],f=top[a];
}
}
int Tquery(int a){
int f=top[a],ans=0;
while (a){
ans+=query(1,1,n,p[f],p[a]);
a=fa[f],f=top[a];
}
return ans;
}
int main(){
scanf("%d%d",&n,&q);
for (int i=1,a;i<n;i++){
scanf("%d",&a);
g.add(a+1,i+1);
g.add(i+1,a+1);
}
Get_Gen_Info(1,0,0);
Get_Top(1,1);
build(1,1,n);
for (int i=0;i<=n;i++)
bh[i].clear();
for (int i=1;i<=q;i++){
scanf("%d%d%d",&L[i],&R[i],&wn[i]);
L[i]++,R[i]++,wn[i]++;
bh[L[i]-1].push_back(i);
bh[R[i]].push_back(i);
}
memset(ans,0,sizeof ans);
for (int i=1;i<=n;i++){
Tupdate(i);
for (int j=0;j<bh[i].size();j++){
int k=bh[i][j];
if (i==L[k]-1)
ans[k]-=Tquery(wn[k]);
else
ans[k]+=Tquery(wn[k]);
}
}
for (int i=1;i<=q;i++)
printf("%d\n",ans[i]%mod);
return 0;
}