本文共 3037 字，大约阅读时间需要 10 分钟。

������

Link

Description

(q) ������������������������ (l,r,z) ������

Solution

������������������������������������������������������������������������������������ u ��� v ��� lca ��������������������������� u ��� v ������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������

��������������������������������������� l ��� r ��������������������� z������������������ z ������������ l ��� r������������������������������������������������������������������������������������������������������������������������������������������������������������������ l ��� r ������������������������������������������

#include
  
   #include
   
    using namespace std;#define lid id<<1#define rid id<<1|1const int Mod=201314;const int N=1e5+7;inline int read(){    int x=0,flag=1; char c=getchar();    while(c<'0'||c>'9'){if(c=='-') flag=0;c=getchar();}    while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-48;c=getchar();}    return flag? x:-x;}struct Que{    int l,pos,op,u;    bool operator <(const Que &X) const{return l
    
     sz[son[u]]) son[u]=v;    }}void Dfs(int u,int tp){    static int tot=0;    top[u]=tp,in[u]=++tot;    if(!son[u]) return ;    Dfs(son[u],tp);    for(int i=head[u];i;i=e[i].next){        int v=e[i].to;        if(v!=son[u]) Dfs(v,v);    }}inline void update(int id){t[id].s=t[lid].s+t[rid].s;}inline void push(int id,int val,int v){    t[id].s=(t[id].s+val*v%Mod)%Mod;    t[id].tag=(t[id].tag+val)%Mod;}void pushdown(int id,int lf,int rf){    int mid=(lf+rf)>>1;    push(lid,t[id].tag,mid-lf+1);    push(rid,t[id].tag,rf-mid);    t[id].tag=0;}int L,R;void modify(int id=1,int lf=1,int rf=n){    if(L<=lf&&rf<=R){push(id,1,rf-lf+1);return ;}    int mid=(lf+rf)>>1;    if(t[id].tag) pushdown(id,lf,rf);    if(L<=mid) modify(lid,lf,mid);    if(R>mid) modify(rid,mid+1,rf);    update(id);}int query(int id=1,int lf=1,int rf=n){    if(L<=lf&&rf<=R) return t[id].s;    int mid=(lf+rf)>>1,ret=0;    if(t[id].tag) pushdown(id,lf,rf);    if(L<=mid) ret=(ret+query(lid,lf,mid))%Mod;    if(R>mid) ret=(ret+query(rid,mid+1,rf))%Mod;    return ret;}void Modify(int u){    while(top[u]!=top[1]){        L=in[top[u]],R=in[u];        modify(),u=fa[top[u]];    }    L=1,R=in[u],modify();}int Query(int u){    int ret=0;    while(top[u]!=top[1]){        L=in[top[u]],R=in[u];        ret=(ret+query())%Mod;        u=fa[top[u]];    }    L=1,R=in[u];    return (ret+query())%Mod;}int main(){    n=read(),m=read();    for(int i=2;i<=n;i++) add(read()+1,i);    for(int i=1;i<=m;i++){        int l=read()+1,r=read()+1,u=read()+1;        q[(i<<1)-1]=(Que){r,i,1,u};        q[i<<1]=(Que){l-1,i,-1,u};    }    sort(q+1,q+1+2*m);    dep[1]=1,dfs(1),Dfs(1,1);    for(int i=1,now=0;i<=2*m;i++){        while(now!=q[i].l) Modify(++now);        ans[q[i].pos]+=q[i].op*Query(q[i].u);        ans[q[i].pos]=(ans[q[i].pos]%Mod+Mod)%Mod;    }    for(int i=1;i<=m;i++)        printf("%dn",ans[i]);}

������