题意
给出一棵树，定义 $\mathrm{dep}[i]$ 为 $i$ 的深度，$\mathrm{LCA}(i,j)$ 为 $i$ 与 $j$ 的最近公共祖先。
有形如 $\text{(l r z)}$ 的询问，求 $\sum\limits_{l\leq i\leq r} \mathrm{dep}[\mathrm{LCA}(i,z)]$ 。
其中点数 $N\le 50000$ ，询问数 $M\le 50000$ 。
题解
用暴力求 $\mathrm{LCA}$ 时，我们可以标记其中一个节点到根节点的路径，剩下一个节点向上走，遇到标记的节点即是 $\mathrm{LCA}$ 。
而一个节点的深度可以认为是它到根节点的距离，令 $1$ 为根，那么求 $\mathrm{LCA(i,j)}$ 的深度可以转化为：将路径 $(1,i)$ 上的节点权值都 $+1$ ，然后查询路径 $(1,j)$ 上的权值和。
考虑差分，将 $[l,r]$ 转化为 $[1,r]-[1,l-1]$ 。我们可以从 $1$ 开始对每个节点到根节点的路径上的权值 $+1$ ，遇到询问再查询路径 $(1,z)$ 上的权值和。
具体实现是将 $l$ 和 $r$ 分开储存，并进行排序。然后从小到大扫一遍，遇到需要查询的就进行查询，然后计算对答案的贡献。
我是把 $l-1$ 存在奇数下标里，把 $r$ 存在偶数下标里，所以对答案的贡献即为 $(-2\times (i \mod 2)+1)\times now$ 。其中 $i$ 是原先的下标， $now$ 是当前查询到的值。
#include<bits/stdc++.h>
#define ha 201314
using namespace std;
inline int read()
{
char ch=getchar();
int f=1,x=0;
while (ch<'0' || ch>'9')
{
if (ch=='-') f=-1;
ch=getchar();
}
while (ch>='0' && ch<='9')
{
x=x*10+ch-'0';
ch=getchar();
}
return f*x;
}
struct Edge {
int next,to;
} edge[50005];
struct Tree {
int left,right,sum,delta;
} tree[200005];
struct Q {
int i,pos,z;
} q[100005];
int cnt,head[50005],n,m,a,b,c,ans[50005];
int dfsord,siz[50005],fa[50005],son[50005],deep[50005],top[50005],id[50005];
inline void add(int u,int v)
{
edge[++cnt].to=v;
edge[cnt].next=head[u];
head[u]=cnt;
}
inline void pushup(int x) { tree[x].sum=(tree[x*2].sum+tree[x*2+1].sum)%ha; }
inline void pushdown(int x)
{
tree[x*2].sum=(tree[x*2].sum+tree[x].delta*(tree[x*2].right-tree[x*2].left))%ha;
tree[x*2+1].sum=(tree[x*2+1].sum+tree[x].delta*(tree[x*2+1].right-tree[x*2+1].left))%ha;
tree[x*2].delta=(tree[x*2].delta+tree[x].delta)%ha;
tree[x*2+1].delta=(tree[x*2+1].delta+tree[x].delta)%ha;
tree[x].delta=0;
}
void build(int x,int l,int r)
{
tree[x].left=l;
tree[x].right=r;
if (r-l>1)
{
int mid=(l+r)>>1;
build(x*2,l,mid);
build(x*2+1,mid,r);
}
}
void update(int x,int l,int r,int delta)
{
if (l<=tree[x].left && r>=tree[x].right)
{
tree[x].sum=(tree[x].sum+delta*(tree[x].right-tree[x].left))%ha;
tree[x].delta=(tree[x].delta+delta)%ha;
}
else
{
if (tree[x].delta) pushdown(x);
int mid=(tree[x].left+tree[x].right)>>1;
if (l<mid) update(x*2,l,r,delta);
if (r>mid) update(x*2+1,l,r,delta);
pushup(x);
}
}
int query(int x,int l,int r)
{
if (l<=tree[x].left && r>=tree[x].right) return tree[x].sum;
else
{
if (tree[x].delta) pushdown(x);
int mid=(tree[x].left+tree[x].right)>>1,ans=0;
if (l<mid) ans=(ans+query(x*2,l,r))%ha;
if (r>mid) ans=(ans+query(x*2+1,l,r))%ha;
return ans;
}
}
void dfs1(int x,int f,int dep)
{
fa[x]=f;
deep[x]=dep;
siz[x]=1;
int mx=0;
for (int i=head[x];i;i=edge[i].next)
{
int y=edge[i].to;
if (y==f) continue;
dfs1(y,x,dep+1);
siz[x]+=siz[y];
if (siz[x]>mx)
{
mx=siz[x];
son[x]=y;
}
}
}
void dfs2(int x,int topf)
{
top[x]=topf;
id[x]=++dfsord;
if (!son[x]) return;
dfs2(son[x],topf);
for (int i=head[x];i;i=edge[i].next)
{
int y=edge[i].to;
if (y==fa[x] || y==son[x]) continue;
dfs2(y,y);
}
}
inline void upRange(int u,int v,int delta)
{
while (top[u]!=top[v])
{
if (deep[top[u]]<deep[top[v]]) swap(u,v);
update(1,id[top[u]],id[u]+1,delta);
u=fa[top[u]];
}
if (deep[u]>deep[v]) swap(u,v);
update(1,id[u],id[v]+1,delta);
}
inline int qRange(int u,int v)
{
int ans=0;
while (top[u]!=top[v])
{
if (deep[top[u]]<deep[top[v]]) swap(u,v);
ans=(ans+query(1,id[top[u]],id[u]+1))%ha;
u=fa[top[u]];
}
if (deep[u]>deep[v]) swap(u,v);
ans=(ans+query(1,id[u],id[v]+1))%ha;
return ans;
}
inline bool cmp(Q x,Q y) { return x.pos<y.pos; } // 按位置先后排序
int main()
{
n=read(); m=read();
for (int i=1;i<n;i++)
{
a=read();
add(a+1,i+1);
}
dfs1(1,0,1);
dfs2(1,1);
build(1,1,n+1);
for (int i=1;i<=m;i++)
{
a=read(); b=read()+1; c=read()+1; // 因为是 l-1 所以不 +1
q[i*2-1].i=i*2-1; q[i*2].i=i*2;
q[i*2-1].pos=a; q[i*2].pos=b;
q[i*2-1].z=q[i*2].z=c;
}
m<<=1;
sort(q+1,q+m+1,cmp);
int j=0;
for (int i=1;i<=m;i++)
{
while (j<q[i].pos) upRange(1,++j,1);
int now=qRange(1,q[i].z);
ans[(q[i].i+1)>>1]+=((q[i].i%2)*-2+1)*now;
ans[(q[i].i+1)>>1]=(ans[(q[i].i+1)>>1]+ha)%ha;
}
m>>=1;
for (int i=1;i<=m;i++) printf("%d\n",ans[i]);
return 0;
}