\(\color{purple}\text{P4211 [LNOI2014]LCA}\)
解题方法
可以发现一个结论：两个点到根节点的重合路径的长度即为他们 \(LCA\) 的深度。所以我们把 \([l,r]\) 之间的点到根节点路径上各加一，再查询 \(z\) 到根节点的路径的值之和即为 \(\sum_{i=l}^{r}\text{dep}[\text{LCA}(i,z)]\) 。显然这个问题（路劲加，路劲查询）可以用树剖求。
但是 \(l,r\) 不固定，我们可以离线用前缀和思想做，\(\sum_{i=l}^{r}\text{dep}[\text{LCA}(i,z)]=\sum_{i=1}^{r}\text{dep}[\text{LCA}(i,z)]-\sum_{i=1}^{l-1}\text{dep}[\text{LCA}(i,z)]\) 。
把问题排序，然后离线做就好了。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N=5e4+10;
int read(){
int x=0,f=1;char c=getchar();
while(c>'9' || c<'0'){if(c=='-')f=-1;c=getchar();}
while(c>='0' && c<='9'){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
return x*f;
}
int n,m;
struct Seg{
int lzy[N<<2],val[N<<2],len[N<<2];
void build(int u,int l,int r){
len[u]=r-l+1;
if(l==r)return;int mid=(l+r)>>1;
build(u<<1,l,mid);build(u<<1|1,mid+1,r);
return;
}
void pushdown(int u){
if(lzy[u]){
val[u<<1]+=lzy[u]*len[u<<1];
val[u<<1|1]+=lzy[u]*len[u<<1|1];
lzy[u<<1]+=lzy[u];lzy[u<<1|1]+=lzy[u];
lzy[u]=0;
}
return;
}
void pushup(int u){val[u]=val[u<<1]+val[u<<1|1];return;}
void update(int u,int l,int r,int L,int R){
if(L<=l && r<=R){val[u]+=len[u];lzy[u]++;return;}
pushdown(u);int mid=(l+r)>>1;
if(L<=mid)update(u<<1,l,mid,L,R);
if(R>mid)update(u<<1|1,mid+1,r,L,R);
pushup(u);return;
}
int query(int u,int l,int r,int L,int R){
if(L<=l && r<=R)return val[u];
pushdown(u);int mid=(l+r)>>1,res=0;
if(L<=mid)res+=query(u<<1,l,mid,L,R);
if(R>mid)res+=query(u<<1|1,mid+1,r,L,R);
return res;
}
}E;
struct Tree{
int head[N],to[N<<1],last[N<<1],tot;
void add(int u,int v){to[++tot]=v,last[tot]=head[u],head[u]=tot;return;}
int maxson[N],dep[N],top[N],sze[N],cnt,dfn[N],fa[N];
void dfs1(int u,int d){
dep[u]=d;sze[u]=1;
for(int i=head[u];i;i=last[i]){
int v=to[i];dfs1(v,d+1);
sze[u]+=sze[v];
if(sze[v]>sze[maxson[u]])maxson[u]=v;
}
return;
}
void dfs2(int u,int t){
top[u]=t;dfn[u]=++cnt;
if(maxson[u])dfs2(maxson[u],t);
for(int i=head[u];i;i=last[i]){
int v=to[i];if(v!=maxson[u])dfs2(v,v);
}
}
void update(int x){
while(x!=0){E.update(1,1,n,dfn[top[x]],dfn[x]);x=fa[top[x]];}
return;
}
int query(int x){
int res=0;
while(x!=0){res+=E.query(1,1,n,dfn[top[x]],dfn[x]);x=fa[top[x]];}
return res;
}
}T;
struct Q{
int tim,id,z,kd;
bool operator<(const Q A)const{return tim<A.tim;}
}q[N<<1];
int ans[N];
int main(){
n=read(),m=read();E.build(1,1,n);
for(int i=2;i<=n;i++){T.fa[i]=read()+1;T.add(T.fa[i],i);}
T.dfs1(1,1);T.dfs2(1,1);
for(int i=1;i<=m;i++){
int l=read()+1,r=read()+1,z=read()+1;
q[2*i-1].id=q[2*i].id=i;
q[2*i-1].tim=l-1,q[2*i-1].z=z,q[2*i-1].kd=-1;
q[2*i].tim=r,q[2*i].z=z,q[2*i].kd=1;
}
sort(q+1,q+2*m+1);int tim=0;
for(int i=1;i<=2*m;i++){
while(tim<q[i].tim){tim++;T.update(tim);}
ans[q[i].id]+=q[i].kd*T.query(q[i].z);
}
for(int i=1;i<=m;i++)printf("%d\n",ans[i]%201314);
return 0;
}