3626: [LNOI2014]LCATime Limit: 10 Sec Memory Limit: 128 MB

Submit: 4191 Solved: 1738

()][Discuss]

Description

给出一个n个节点的有根树（编号为0到n-1，根节点为0）。一个点的深度定义为这个节点到根的距离+1。

设dep[i]表示点i的深度，LCA(i,j)表示i与j的最近公共祖先。

有q次询问，每次询问给出l r z，求sigma_{l<=i<=r}dep[LCA(i,z)]。

（即，求在[l,r]区间内的每个节点i与z的最近公共祖先的深度之和）

Input

第一行2个整数n q。

接下来n-1行，分别表示点1到点n-1的父节点编号。

接下来q行，每行3个整数l r z。

Output

输出q行，每行表示一个询问的答案。每个答案对201314取模输出

Sample Input

5 2

0

0

1

1

1 4 3

1 4 2

Sample Output

8

5

HINT

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

---

本来是想主席树在线做的，被asuldb神仙hack了tql！%%%%%%%%%%%%%%%%%%

所以离线就行了啊

lca的深度和可以转化成对于路径上的每一个点，它的子树内l到r 的点的个数和，主席树就爆内存GG了

离线下来以后1~n顺序加点前如果有答案用树剖跑一下单条链，这两个操作O(nlog^2n)的,50000毫无压力

---

#include
    
     #include
     
      #include
      
       #include
       
        #define LL long long#define M 500001#define N 201314#define max(a,b) ((a)>(b)? (a):(b))#define min(a,b) ((a)<(b)? (a):(b))#define update(a) d[a]=d[a<<1]+d[(a<<1)|1]using namespace std;int i,m,n,j,k,a[M], dfn[M], cnt, top[M], f[M], ver[M], nex[M], head[M],de[M], d[M], pre[M], q, s[M], wson[M],ans[M], lazy[M],tl=1,tr=1;struct vv{    int l,r,z,w;} b[M], c[M];bool cmpl(vv a,vv b){return a.l
        
         >1;    d[now<<1]=(d[now<<1]+(mid-l+1)*lazy[now])%N;    d[(now<<1)|1]=(d[(now<<1)|1]+(r-mid)*lazy[now])%N;    lazy[now<<1]=(lazy[now<<1]+lazy[now])%N;    lazy[(now<<1)|1]=(lazy[(now<<1)|1]+lazy[now])%N;    lazy[now]=0;}void dfs1(int now){    s[now]=1; wson[now]=n+2;    for(int i=head[now];i;i=nex[i])    {        int t=ver[i]; dfs1(t);        if(s[t]>s[wson[now]]) wson[now]=t;        s[now]+=s[t];    }}void dfs2(int now,int topp){    cnt+=1;    dfn[now]=cnt; top[now]=topp;    if(wson[now]!=n+2) dfs2(wson[now],topp);    for(int i=head[now];i;i=nex[i])    {        int t=ver[i];        if(dfn[t]) continue;        dfs2(t, t);    }}void dd(int now,int l,int r,int ll,int rr,int z){    if(l>=ll && r<=rr)     {        d[now]+=((r-l+1)*z)%N;        lazy[now]+=z;        return;    }     int mid=(l+r)>>1;    down(now,l,r);    if(ll<=mid) dd(now*2,l,mid,ll,rr,z);    if(rr>mid) dd(now*2+1,mid+1,r,ll,rr,z);    update(now);}void ad(int x){    while(top[x]!=0)    {        dd(1,1,n,dfn[top[x]],dfn[x],1);        x=f[top[x]];    }    dd(1,1,n,1,dfn[x],1);}int qsum(int now,int l,int r,int ll,int rr){    if(l>=ll && r<=rr) return d[now];    int mid=(l+r)>>1,ans=0;    down(now,l,r);    if(ll<=mid) ans=(ans+qsum(now*2,l,mid,ll,rr))%N;    if(rr>mid) ans=(ans+qsum(now*2+1, mid+1,r,ll,rr))%N;    return ans;}int find(int x){    int ans=0;    while(top[x]!=0)    {        ans=(ans+qsum(1,1,n,dfn[top[x]],dfn[x]))%N;        x=f[top[x]];    }    ans=(ans+qsum(1,1,n,1,dfn[x]))%N;    return ans;}int main(){    scanf("%d%d",&n,&q);    for(i=1;i