Lvat_s Blog

首先我们可以离线做

考虑每次把一条链上的权值全部加上1，然后询问z到根的值就是这个LCA的和

然后离线排序树剖一下直接做就好了

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;
 
const int N=50005,Mod=201314;
 
int n,q,en,fa[N],h[N],cnt,dep[N],top[N],segn,siz[N],son[N],id[N];
 
struct Ask{
int z,ans1,ans2;
}Qu[N];
 
struct Option{
int id,p,flag;
friend bool operator<(Option A,Option B){return A.p<B.p;}
}Opt[2*N];
 
struct Edge{
int b,next;
}e[N];
 
void AddEdge(int sa,int sb){
e[++en].b=sb;
e[en].next=h[sa];
h[sa]=en;
}
 
struct SegTree{
int l,r,sum,tag;
}tree[4*N];
 
void Pushup(int rt){tree[rt].sum=(tree[rt<<1].sum+tree[rt<<1|1].sum)%Mod;}
 
void Pushdown(int rt){
if(tree[rt].tag){
    tree[rt<<1].tag=(tree[rt<<1].tag+tree[rt].tag)%Mod;
    tree[rt<<1|1].tag=(tree[rt<<1|1].tag+tree[rt].tag)%Mod;
    tree[rt<<1].sum=(tree[rt<<1].sum+tree[rt].tag*(tree[rt<<1].r-tree[rt<<1].l+1))%Mod;
    tree[rt<<1|1].sum=(tree[rt<<1|1].sum+tree[rt].tag*(tree[rt<<1|1].r-tree[rt<<1|1].l+1))%Mod;
    tree[rt].tag=0;
}
}
 
void Build(int rt,int l,int r){
tree[rt].l=l;
tree[rt].r=r;
if(l==r){tree[rt].sum=0;tree[rt].tag=0;return;}
int mid=l+r>>1;
Build(rt<<1,l,mid);
Build(rt<<1|1,mid+1,r);
}
 
void Modify(int rt,int l,int r,int val){
if(l<=tree[rt].l && tree[rt].r<=r){
    tree[rt].tag=(tree[rt].tag+val)%Mod;
    tree[rt].sum=(tree[rt].sum+val*(tree[rt].r-tree[rt].l+1))%Mod;
    return;
}
Pushdown(rt);
int mid=tree[rt].l+tree[rt].r>>1;
if(l<=mid)Modify(rt<<1,l,r,val);
if(r>mid)Modify(rt<<1|1,l,r,val);
Pushup(rt);
}
 
int Query(int rt,int l,int r){
if(l<=tree[rt].l && tree[rt].r<=r)return tree[rt].sum;
int mid=tree[rt].l+tree[rt].r>>1,ans=0;
Pushdown(rt);
if(l<=mid)ans=(ans+Query(rt<<1,l,r))%Mod;
if(r>mid)ans=(ans+Query(rt<<1|1,l,r))%Mod;
return ans;
}
 
void dfs1(int u){
dep[u]=dep[fa[u]]+1;
siz[u]=1;
son[u]=0;
for(int i=h[u];i;i=e[i].next){
    int v=e[i].b;
    if(v==fa[u])continue;
    dfs1(v);
    siz[u]+=siz[v];
    if(siz[son[u]]<siz[v])son[u]=v;
}
}
 
void dfs2(int u,int ux){
top[u]=ux;
id[u]=++segn;
if(!son[u])return;
dfs2(son[u],ux);
for(int i=h[u];i;i=e[i].next){
    int v=e[i].b;
    if(son[u]==v || fa[u]==v)continue;
    dfs2(v,v);
}
}
 
void Update(int x){
while(top[x]!=top[1]){
    Modify(1,id[top[x]],id[x],1);
    x=fa[top[x]];
}
Modify(1,id[1],id[x],1);
}
 
int Solve(int x){
int ans=0;
while(top[x]!=top[1]){
    ans=(ans+Query(1,id[top[x]],id[x]))%Mod;
    x=fa[top[x]];
}
return (ans+Query(1,id[1],id[x]))%Mod;
}
 
int main(){
freopen("3626.in","r",stdin);
freopen("3626.out","w",stdout);
scanf("%d %d",&n,&q);
for(int i=2;i<=n;i++){scanf("%d",&fa[i]);fa[i]++;AddEdge(fa[i],i);}
dfs1(1);
dfs2(1,1);
Build(1,1,n);
for(int i=1;i<=q;i++){
    int x,y,z;
    scanf("%d %d %d",&x,&y,&z);
    x++;y++;z++;
    Qu[i].z=z;
    Opt[++cnt].id=i;
    Opt[cnt].p=x-1;
    Opt[cnt].flag=0;
    Opt[++cnt].id=i;
    Opt[cnt].p=y;
    Opt[cnt].flag=1;
}
sort(Opt+1,Opt+cnt+1);
int Now=1;
for(int i=1;i<=cnt;i++){
    while(Now<=Opt[i].p){Update(Now);Now++;}
    if(Opt[i].flag)Qu[Opt[i].id].ans2=Solve(Qu[Opt[i].id].z);
    else Qu[Opt[i].id].ans1=Solve(Qu[Opt[i].id].z);
}
for(int i=1;i<=q;i++){
    printf("%d\n",(Qu[i].ans2-Qu[i].ans1+Mod)%Mod);
}
return 0;
}