复习物理时突然有了这个题的做法。
我也不知道为啥学物理会想到这个
一个不用转化、不用扫描线、不用$LCT$树剖的$chuan$新做法：直接分块！
每个块开个$vector$记录询问。
散块直接暴力。整块把该询问丢进$vector$里。
询问处理完后处理每个块：
记$l,r$为块的左右端点，对每个点$x$算出$\sum\limits_{i=l}^rdeep[lca(i,x)]$，最后把属于该块的每个询问点的贡献加进去即可。
$dfs$一遍树。考虑每个点为$lca$的贡献。记$siz(i)$为$i$子树中编号在$[l,r]$的点的个数。
点$i$会对其整棵子树有$deep(i)\times siz(i)$的贡献，然后对其每个儿子$x$，要容斥减去$deep(i)\times siz(x)$的不合法贡献。
子树加，$dfs$序+差分即可。
空间$O(n\sqrt{n})$，用$O(1)LCA$的话时间为$O(n\sqrt{n})$。
用$Tarjan\ LCA$被卡空间了用树剖$LCA$被卡时间了被迫现学的$RMQ\ LCA$，做LCA题学LCA没毛病
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <vector>
#define maxn 50005
#define inf 0x3f3f3f3f
const int mod = 201314;
using namespace std;
inline int read(){
int x=0,y=0;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')y=1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return y?-x:x;
}
int siz[maxn],h[maxn],seg[maxn],pos[maxn],low[maxn],deep[maxn]={inf,1},num,cnt;
int be[maxn],a[maxn],ans[maxn],f[maxn<<1][22],fir[maxn],lg[maxn<<1],all;
struct edge{
int pre,to;
}e[maxn];
inline int cmp(int x,int y){return deep[x]<deep[y]?x:y;}
inline void add(int from,int to){
e[++num].pre=h[from],h[from]=num,e[num].to=to;
}
void dfs(int node=1){
f[fir[node]=++all][0]=pos[seg[node]=++cnt]=node;
int x;
for(register int i=h[node];i;i=e[i].pre){
x=e[i].to,deep[x]=deep[node]+1,dfs(x);
f[++all][0]=node;
}
low[node]=cnt;
}
void ST(){
for(register int i=2;i<=all;++i)lg[i]=lg[i>>1]+1;
for(register int j=1;j<=lg[all];++j)
for(register int i=1;i+(1<<(j-1))<=all;++i)
f[i][j]=cmp(f[i][j-1],f[i+(1<<(j-1))][j-1]);
}
inline int query(int l,int r){
if(l>r)swap(l,r);
int len=lg[r-l+1];
return cmp(f[l][len],f[r-(1<<len)+1][len]);
}
inline int lca(int x,int y){
return query(fir[x],fir[y]);
}
#define modify(x,d) a[seg[x]]+=d,a[low[x]+1]-=d
#define id(x) (x>=l&&x<=r)
struct BLOCK{
int l,r;
vector<pair<int,int> >q;
void calc(int node=1){
siz[node]=id(node);
int x;
for(register int i=h[node];i;i=e[i].pre){
x=e[i].to;
calc(x),siz[node]+=siz[x];
}
modify(node,deep[node]*siz[node]);
for(register int i=h[node];i;i=e[i].pre){
x=e[i].to;
modify(x,(-deep[node]*siz[x]));
}
}
void solve(){
calc();
for(register int i=1;i<=cnt;++i)a[i]+=a[i-1];
for(vector<pair<int,int> >::iterator iter=q.begin();iter!=q.end();++iter)
(ans[iter->second]+=a[iter->first])%=mod;
}
}b[250];
inline void odd(int l,int r,int x,int p){
for(register int i=l;i<=r;++i)ans[p]+=deep[lca(i,x)];
}
int main(){
int n=read(),m=read(),l,r,x,sq=sqrt(n),len=n/sq+bool(n%sq);
for(register int i=2;i<=n;++i)add(read()+1,i);
dfs(),ST();
for(register int i=1;i<=len;++i){
b[i].l=b[i-1].r+1,b[i].r=min(b[i].l+sq-1,n);
for(register int j=b[i].l;j<=b[i].r;++j)
be[j]=i;
}
for(register int i=1;i<=m;++i){
l=read()+1,r=read()+1,x=read()+1;
if(be[l]==be[r]){odd(l,r,x,i);}
else {
odd(l,b[be[l]].r,x,i);
odd(b[be[r]].l,r,x,i);
x=seg[x];
for(register int j=be[l]+1;j<be[r];++j)
b[j].q.push_back((pair<int,int>){x,i});
}
}
for(register int i=1;i<=len;++i)memset(a,0,sizeof a),b[i].solve();
for(register int i=1;i<=m;++i)printf("%d\n",(ans[i]%mod+mod)%mod);
}
