百度空间马上要下架的说，赶快把最后一点题解补完，然后搬家
这是一道不错的题，首先注意询问是满足区间减法的，我们把他变成前缀和表示设我们询问[1,r]中的点和z的LCA深度和，假设我们确定一个根，不难发现一个有趣的事情点z和点i的LCA深度=z和i到根公共路径（LCA到根的路径）上点的个数！也就是说，当我们查询时，我们只要知道，[1,r]上的点到根路径上的点在z到根上出现的次数和所以不难想到离线的做法，按照编号的顺序，每次做到点i，就把点i到根路径上点权值+1询问的时候我们只要查询z到根路径上点权值和即可，显然我们可以用树链剖分+线段树维护
1 const mo=201314; 2 type node=record 3 po,next:longint; 4 end; 5 que=record 6 x,y,p,op:longint; 7 end; 8 9 var p,c,top,ans,fa,size:array[0..50010] of longint; 10 tree,lazy:array[0..50010*4] of longint; 11 q:array[0..100010] of que; 12 e:array[0..50010] of node; 13 t,l,r,x,i,j,n,m:longint; 14 15 procedure swap(var a,b:que); 16 var c:que; 17 begin 18 c:=a; 19 a:=b; 20 b:=c; 21 end; 22 23 procedure add(x,y:longint); 24 begin 25 e[i].po:=y; 26 e[i].next:=p[x]; 27 p[x]:=i; 28 end; 29 30 procedure dfs1(x:longint); 31 var i,y:longint; 32 begin 33 size[x]:=1; 34 i:=p[x]; 35 while i<>0 do 36 begin 37 y:=e[i].po; 38 fa[y]:=x; 39 dfs1(y); 40 size[x]:=size[x]+size[y]; 41 i:=e[i].next; 42 end; 43 end; 44 45 procedure dfs2(x:longint); 46 var i,y,q:longint; 47 begin 48 inc(t); 49 c[x]:=t; 50 q:=n+1; 51 i:=p[x]; 52 while i<>0 do 53 begin 54 y:=e[i].po; 55 if size[y]>size[q] then q:=y; 56 i:=e[i].next; 57 end; 58 if q<>n+1 then 59 begin 60 top[q]:=top[x]; 61 dfs2(q); 62 end; 63 i:=p[x]; 64 while i<>0 do 65 begin 66 y:=e[i].po; 67 if y<>q then 68 begin 69 top[y]:=y; 70 dfs2(y); 71 end; 72 i:=e[i].next; 73 end; 74 end; 75 76 procedure sort(l,r:longint); 77 var i,j,y:longint; 78 begin 79 i:=l; 80 j:=r; 81 y:=q[(l+r) shr 1].y; 82 repeat 83 while q[i].yj) then 86 begin 87 swap(q[i],q[j]); 88 inc(i); 89 dec(j); 90 end; 91 until i>j; 92 if l =r) then111 begin112 tree[i]:=tree[i]+r-l+1;113 lazy[i]:=lazy[i]+1;114 end115 else begin116 if lazy[i]>0 then push(i,l,r);117 m:=(l+r) shr 1;118 if x<=m then work(i*2,l,m,x,y);119 if y>m then work(i*2+1,m+1,r,x,y);120 tree[i]:=(tree[i*2]+tree[i*2+1]) mod mo;121 end;122 end;123 124 function getans(i,l,r,x,y:longint):longint;125 var m,s:longint;126 begin127 if (x<=l) and (y>=r) then exit(tree[i])128 else begin129 if lazy[i]>0 then push(i,l,r);130 m:=(l+r) shr 1;131 s:=0;132 if x<=m then s:=s+getans(i*2,l,m,x,y);133 if y>m then s:=s+getans(i*2+1,m+1,r,x,y);134 exit(s);135 end;136 end;137 138 procedure ins(x:longint);139 begin140 while top[x]<>-1 do141 begin142 work(1,1,n,c[top[x]],c[x]);143 x:=fa[top[x]];144 end;145 work(1,1,n,1,c[x]);146 end;147 148 function ask(x:longint):longint;149 begin150 ask:=0;151 while top[x]<>-1 do152 begin153 ask:=ask+getans(1,1,n,c[top[x]],c[x]);154 x:=fa[top[x]];155 end;156 ask:=(ask+getans(1,1,n,1,c[x])) mod mo;157 end;158 159 begin160 readln(n,m);161 for i:=1 to n-1 do162 begin163 read(x);164 add(x,i);165 end;166 dfs1(0);167 top[0]:=-1;168 dfs2(0);169 t:=0;170 for i:=1 to m do171 begin172 readln(l,r,x);173 inc(t);174 q[t].x:=x; q[t].y:=l-1;175 q[t].p:=i; q[t].op:=-1;176 inc(t);177 q[t].x:=x; q[t].y:=r;178 q[t].p:=i; q[t].op:=1;179 end;180 sort(1,t);181 j:=0;182 for i:=1 to t do183 begin184 while (j