BZOJ_3626_[LNOI2014]LCA_离线+树剖
题意：
给出一个n个节点的有根树（编号为0到n-1，根节点为0）。一个点的深度定义为这个节点到根的距离+1。
设dep[i]表示点i的深度，LCA(i,j)表示i与j的最近公共祖先。
有q次询问，每次询问给出l r z，求$\sum\limits_{l\le i\le r}dep(LCA(i,z))$。
（即，求在[l,r]区间内的每个节点i与z的最近公共祖先的深度之和）
分析：
求$\sum\limits_{l\le i\le r}dep(LCA(i,z))$相当于把[l,r]区间内所有点依次插入。
每次把点到1路径上所有点+1，可以发现z到1路径上的点权和即为所求。
并且该操作具有区间可减性。那么我们把所有询问拆成[0~l-1],[0~r]两部分。
排个序离线计算。
代码：
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define N 100050
#define LL long long
#define ls p<<1
#define rs p<<1|1
int head[N],to[N<<1],nxt[N<<1],cnt,n,m,r,mod=201314;
int t[N<<2],lz[N<<2],tot;
int siz[N],top[N],son[N],fa[N],dep[N],idx[N];
LL now,ans[N];
struct A{
int pos,z,flg,id;
}a[N];
bool cmp(const A &x,const A &y){
return x.pos<y.pos;
}
inline void add(int u,int v){
to[++cnt]=v;nxt[cnt]=head[u];head[u]=cnt;
}
void dfs1(int x,int y){
fa[x]=y;dep[x]=dep[y]+1;siz[x]=1;
for(int i=head[x];i;i=nxt[i]){
if(to[i]!=y){
dfs1(to[i],x);
siz[x]+=siz[to[i]];
if(siz[to[i]]>siz[son[x]])son[x]=to[i];
}
}
}
void dfs2(int x,int t){
top[x]=t;idx[x]=++tot;
if(son[x])dfs2(son[x],t);
for(int i=head[x];i;i=nxt[i]){
if(to[i]!=fa[x]&&to[i]!=son[x])dfs2(to[i],to[i]);
}
}
void pud(int l,int r,int p){
if(!lz[p])return ;
int mid=l+r>>1;
lz[ls]=(lz[ls]+lz[p])%mod;
lz[rs]=(lz[rs]+lz[p])%mod;
t[ls]=(t[ls]+lz[p]*(mid-l+1))%mod;
t[rs]=(t[rs]+lz[p]*(r-mid))%mod;
lz[p]=0;
}
void up(int l,int r,int x,int y,int c,int p){
if(x<=l&&r<=y){
lz[p]=(lz[p]+c)%mod;
t[p]=(t[p]+c*(r-l+1))%mod;return ;
}
pud(l,r,p);
int mid=l+r>>1;
if(x<=mid)up(l,mid,x,y,c,ls);
if(y>mid)up(mid+1,r,x,y,c,rs);
t[p]=(t[ls]+t[rs])%mod;
}
int query(int l,int r,int x,int y,int p){
if(x<=l&&r<=y){
return t[p];
}
pud(l,r,p);
int mid=l+r>>1;
int re=0;
if(x<=mid)re=(re+query(l,mid,x,y,ls))%mod;
if(y>mid)re=(re+query(mid+1,r,x,y,rs))%mod;
return re;
}
void insert(int x){
int y=1;
while(top[x]!=top[y]){
if(dep[top[x]]>dep[top[y]])swap(x,y);
up(1,n,idx[top[y]],idx[y],1,1);
y=fa[top[y]];
}if(dep[x]<dep[y])swap(x,y);
up(1,n,idx[y],idx[x],1,1);
}
LL ask(int x){
LL re=0;
int y=1;
while(top[x]!=top[y]){
if(dep[top[x]]>dep[top[y]])swap(x,y);
re+=query(1,n,idx[top[y]],idx[y],1);
re%=mod;
y=fa[top[y]];
}if(dep[x]<dep[y])swap(x,y);
re+=query(1,n,idx[y],idx[x],1);
re%=mod;
return re;
}
int main(){
scanf("%d%d",&n,&m);
int x;
for(int i=2;i<=n;i++){
scanf("%d",&x);x++;
add(x,i);add(i,x);
}
dfs1(1,0);
dfs2(1,1);
for(int i=1;i<=m;i++){
scanf("%d%d%d",&a[i].pos,&a[i+m].pos,&a[i].z);
a[i+m].pos++;a[i].z++;
a[i+m].z=a[i].z;a[i].id=a[i+m].id=i;a[i+m].flg=1;
}
sort(a+1,a+m+m+1,cmp);
int dir=0;
for(int i=1;i<=m+m;i++){
if(dir==a[i].pos){
ans[a[i].id+a[i].flg*m]=ask(a[i].z);continue;
}else{
for(int j=dir+1;j<=a[i].pos;j++){
insert(j);
}
ans[a[i].id+a[i].flg*m]=ask(a[i].z);dir=a[i].pos;
}
}
for(int i=1;i<=m;i++){
printf("%lld\n",(ans[i+m]-ans[i]+mod)%mod);
} }
/* 5 2
0
0
1
1
1 4 3
1 4 2
*/