题目大意

给出一棵$n$个节点的有根树，编号为$0$到$n-1$，根节点为$0$

询问$m$次，每次询问给出区间$[l,r]$和节点编号$z$，求$$\sum_{l\leqslant i\leqslant r}deep[lca(i,z)]$$

每个答案对$201314$取模输出

数据范围

共$5$组数据，$n$与$m$的规模分别为$10000,20000,30000,40000,50000$

题解

http://blog.csdn.net/popoqqq/article/details/38823457

http://blog.csdn.net/alan_cty/article/details/51649011

程序

#include<cstdio>
#include<cmath>
#include<cstring>
#include<cctype>
#include<algorithm>
#define lp p<<1
#define rp p<<1|1
#define mod 201314
#define N 50500
#define For(i,l,r) for(int i=l;i<=r;++i)
#define goedge(i,x) for(int i=last[x];i;i=e[i].next)
inline int read(){
    int x=0;char ch=getchar();
    while (!isdigit(ch)) ch=getchar();
    while (isdigit(ch)) {x=x*10+ch-48;ch=getchar();}
    return x;
}
using namespace std;

int n,m,et,cnt;
int size[N],f[N],deep[N],top[N],pos[N];
struct edge{int to,next;}e[N];
struct answer{int z,ans1,ans2;}q[N];
struct data{int id,pos;bool flag;}a[2*N];
struct seg{int sum,tag;}t[4*N];
int last[N];

inline bool cmp(data a,data b){
    return a.pos<b.pos;
}
inline void addedge(int u,int v){
    e[++et]=(edge){v,last[u]};last[u]=et;
}
inline void pushdown(int p,int wl,int wr){
    if (wl==wr || !t[p].tag) return;
    int tmp=t[p].tag,mid=(wl+wr)>>1;t[p].tag=0;
    t[lp].sum+=(mid-wl+1)*tmp,t[rp].sum+=(wr-mid)*tmp;
    t[lp].tag+=tmp;t[rp].tag+=tmp;
}

void dfs(int x){
    size[x]=1;
    goedge(i,x){
        if (e[i].to==f[x]) continue;
        deep[e[i].to]=deep[x]+1;
        f[e[i].to]=x;
        dfs(e[i].to);
        size[x]+=size[e[i].to];
    }
}
void gochain(int x,int chain){
    top[x]=chain;pos[x]=++cnt;
    int k=n;
    goedge(i,x)
        if (e[i].to!=f[x] && size[e[i].to]>size[k]) k=e[i].to;
    if (k!=n) gochain(k,chain);
    goedge(i,x)
        if (e[i].to!=f[x] && e[i].to!=k) gochain(e[i].to,e[i].to);
}

void update(int p,int wl,int wr,int l,int r){
    pushdown(p,wl,wr);
    if (wl==l && wr==r){
        t[p].tag++,t[p].sum+=wr-wl+1;
        return;
    }
    int mid=(wl+wr)>>1;
    if (l<=mid) update(lp,wl,mid,l,min(mid,r));
    if (r>mid) update(rp,mid+1,wr,max(mid+1,l),r);
    t[p].sum=t[lp].sum+t[rp].sum;
}
inline void solve_update(int x,int y){
    while (top[x]!=top[y]){
        update(1,1,n,pos[top[x]],pos[x]);
        x=f[top[x]];
    }
    update(1,1,n,pos[y],pos[x]);
}
int query(int p,int wl,int wr,int l,int r){
    pushdown(p,wl,wr);
    if (wl==l && wr==r) return t[p].sum;
    int mid=(wl+wr)>>1;
    int s1=0,s2=0;
    if (l<=mid) s1=query(lp,wl,mid,l,min(mid,r));
    if (r>mid) s2=query(rp,mid+1,wr,max(mid+1,l),r);
    return s1+s2;
}
inline int solve_query(int x,int y){
    int sum=0;
    while (top[x]!=top[y]){
        sum=(sum+query(1,1,n,pos[top[x]],pos[x]))%mod;
        x=f[top[x]];
    }
    sum=(sum+query(1,1,n,pos[y],pos[x]))%mod;
    return sum;
}

int main(){
    n=read(),m=read();
    For(i,1,n-1){
        int u=read();
        addedge(u,i);
    }
    For(i,1,m){
        int l=read(),r=read();
        q[i].z=read();
        a[2*i-1]=(data){i,l-1,0};
        a[2*i]=(data){i,r,1};
    }
    sort(a+1,a+2*m+1,cmp);
    dfs(0);gochain(0,0);
    int now=-1;
    For(i,1,2*m){
        while (now<a[i].pos){
            now++;
            solve_update(now,0);
        }
        if (!a[i].flag) q[a[i].id].ans1=solve_query(q[a[i].id].z,0);
        else q[a[i].id].ans2=solve_query(q[a[i].id].z,0);
    }
    For(i,1,m)
        printf("%d\n",(q[i].ans2-q[i].ans1+mod)%mod);
    return 0;
}