( ext{Solution})
思路很巧。。。
可以发现，(dep[x]) 可以转化为求根节点到 (x) 的路径中有多少个点。这样求 (dep[ ext{LCA}(x,y)]) 可以转化为在根节点到 (x) 的路径上每个点加 (1)，再数根节点到 (y) 的和。
我们将询问拆成 ((l-1,z),(r,z))，再把所有询问按第一关键字从小到大排序，一一将 (1) 到 (n) 的点加进去。关于根节点到 (x) 的路径，可以用树链剖分维护，时间复杂度 (mathcal O(mlog^2n))。
( ext{Code})
#include <cstdio>
#define rep(i,_l,_r) for(register signed i=(_l),_end=(_r);i<=_end;++i)
#define fep(i,_l,_r) for(register signed i=(_l),_end=(_r);i>=_end;--i)
#define erep(i,u) for(signed i=head[u],v=to[i];i;i=nxt[i],v=to[i])
#define efep(i,u) for(signed i=Head[u],v=to[i];i;i=nxt[i],v=to[i])
#define print(x,y) write(x),putchar(y)
template <class T> inline T read(const T sample) {
T x=0; int f=1; char s;
while((s=getchar())>'9'||s<'0') if(s=='-') f=-1;
while(s>='0'&&s<='9') x=(x<<1)+(x<<3)+(s^48),s=getchar();
return x*f;
}
template <class T> inline void write(const T x) {
if(x<0) return (void) (putchar('-'),write(-x));
if(x>9) write(x/10);
putchar(x%10^48);
}
template <class T> inline T Max(const T x,const T y) {if(x>y) return x; return y;}
template <class T> inline T Min(const T x,const T y) {if(x<y) return x; return y;}
template <class T> inline T fab(const T x) {return x>0?x:-x;}
template <class T> inline T gcd(const T x,const T y) {return y?gcd(y,x%y):x;}
template <class T> inline T lcm(const T x,const T y) {return x/gcd(x,y)*y;}
template <class T> inline T Swap(T &x,T &y) {x^=y^=x^=y;}
#include <algorithm>
using namespace std;
const int maxn=5e4+5,mod=201314;
int cnt,head[maxn],nxt[maxn<<1],to[maxn<<1],n,q,tot,siz[maxn],son[maxn],dfn[maxn],tp[maxn],f[maxn],t[maxn<<2],la[maxn<<2],dep[maxn],ans[maxn],Dfn;
struct node {int p,x,id,sign;} s[maxn<<1];
bool cmp(node a,node b) {return a.p<b.p;}
void addEdge(int u,int v) {
nxt[++cnt]=head[u],to[cnt]=v,head[u]=cnt;
}
void dfs1(int u) {
siz[u]=1;
erep(i,u) {
f[v]=u; dep[v]=dep[u]+1;
dfs1(v);
siz[u]+=siz[v];
if(siz[v]>siz[son[u]]) son[u]=v;
}
}
void dfs2(int u,int t) {
tp[u]=t; dfn[u]=++Dfn;
if(!son[u]) return;
dfs2(son[u],t);
erep(i,u) if(v^son[u]) dfs2(v,v);
}
void pushDown(int o,int l,int r) {
if(!la[o]) return;
int mid=l+r>>1;
la[o<<1]+=la[o]; la[o<<1|1]+=la[o];
t[o<<1]+=(mid-l+1)*la[o]; t[o<<1|1]+=(r-mid)*la[o];
la[o]=0;
}
void modify(int o,int l,int r,int L,int R,int k) {
if(l>R||r<L) return;
if(l>=L&&r<=R) {t[o]+=k*(r-l+1); la[o]+=k; return;}
int mid=l+r>>1;
pushDown(o,l,r);
modify(o<<1,l,mid,L,R,k); modify(o<<1|1,mid+1,r,L,R,k);
t[o]=t[o<<1]+t[o<<1|1];
}
int query(int o,int l,int r,int L,int R) {
if(l>R||r<L) return 0;
if(l>=L&&r<=R) return t[o];
int mid=l+r>>1;
pushDown(o,l,r);
return query(o<<1,l,mid,L,R)+query(o<<1|1,mid+1,r,L,R);
}
void update(int u,int v) {
while(tp[u]^tp[v])
if(dep[tp[u]]<dep[tp[v]]) {
modify(1,1,n,dfn[tp[v]],dfn[v],1);
v=f[tp[v]];
}
else {
modify(1,1,n,dfn[tp[u]],dfn[u],1);
u=f[tp[u]];
}
if(dfn[u]<dfn[v]) modify(1,1,n,dfn[u],dfn[v],1);
else modify(1,1,n,dfn[v],dfn[u],1);
}
int ask(int u,int v) {
int r=0;
while(tp[u]^tp[v])
if(dep[tp[u]]<dep[tp[v]]) {
r=(r+query(1,1,n,dfn[tp[v]],dfn[v]))%mod;
v=f[tp[v]];
}
else {
r=(r+query(1,1,n,dfn[tp[u]],dfn[u]))%mod;
u=f[tp[u]];
}
if(dfn[u]<dfn[v]) r=(r+query(1,1,n,dfn[u],dfn[v]))%mod;
else r=(r+query(1,1,n,dfn[v],dfn[u]))%mod;
return r;
}
int main() {
int l,r,z,pos=0;
n=read(9),q=read(9);
rep(i,2,n) addEdge(read(9)+1,i);
rep(i,1,q) {
l=read(9)+1,r=read(9)+1,z=read(9)+1;
s[++tot]=(node) {l-1,z,i,-1}; s[++tot]=(node) {r,z,i,1};
}
sort(s+1,s+tot+1,cmp);
dfs1(1),dfs2(1,1);
rep(i,1,tot) {
while(pos<s[i].p) update(1,++pos);
ans[s[i].id]=(ans[s[i].id]+s[i].sign*ask(1,s[i].x)%mod+mod)%mod;
}
rep(i,1,q) print(ans[i],'
');
return 0;
}