乐子
笑点解析：单log疯狂卡常才卡过那两双log做法。
全局平衡二叉树解法。
考虑差分，然后挂扫描线。\(dep_{LCA(x,y)}\)实际上就是将\(x\)到根的节点权值加1，然后求\(y\)到根的节点的权值和。
然后就是全局平衡二叉树的板子，标记永久化写就好了。
应该会抽时间写一个全局平衡二叉树的学习笔记，会把这道题当做例题，所以这里就不多说了。
点此查看代码
#include<bits/stdc++.h>
#include<bits/extc++.h>
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;
using namespace std;
#define rep(i,s,t,p) for(register int i = s;i <= t; i += p)
#define drep(i,s,t,p) for(register int i = s;i >= t; i -= p)
namespace IO{
#ifdef LOCAL
FILE*Fin(fopen("in.in","r")),*Fout(fopen("out.out","w"));
#else
FILE*Fin(stdin),*Fout(stdout);
#endif
class qistream{static const size_t SIZE=1<<27,BLOCK=64;FILE*fp;char buf[SIZE];int p;public:qistream(FILE*_fp=stdin):fp(_fp),p(0){fread_unlocked(buf+p,1,SIZE-p,fp);}void flush(){memmove(buf,buf+p,SIZE-p),fread_unlocked(buf+SIZE-p,1,p,fp),p=0;}qistream&operator>>(char&str){str=getch();while(isspace(str))str=getch();return*this;}template<class T>qistream&operator>>(T&x){x=0;p+BLOCK>=SIZE?flush():void();bool flag=false;for(;!isdigit(buf[p]);++p)flag=buf[p]=='-';for(;isdigit(buf[p]);++p)x=x*10+buf[p]-'0';x=flag?-x:x;return*this;}char getch(){return buf[p++];}qistream&operator>>(char*str){char ch=getch();while(ch<=' ')ch=getch();for(int i=0;ch>' ';++i,ch=getch())str[i]=ch;return*this;}}qcin(Fin);
class qostream{static const size_t SIZE=1<<27,BLOCK=64;FILE*fp;char buf[SIZE];int p;public:qostream(FILE*_fp=stdout):fp(_fp),p(0){}~qostream(){fwrite_unlocked(buf,1,p,fp);}void flush(){fwrite_unlocked(buf,1,p,fp),p=0;}template<class T>qostream&operator<<(T x){int len=0;p+BLOCK>=SIZE?flush():void();x<0?(x=-x,buf[p++]='-'):0;do buf[p+len]=x%10+'0',x/=10,++len;while(x);for(int i=0,j=len-1;i<j;++i,--j)swap(buf[p+i],buf[p+j]);p+=len;return*this;}qostream&operator<<(char x){putch(x);return*this;}void putch(char ch){p+BLOCK>=SIZE?flush():void();buf[p++]=ch;}qostream&operator<<(char*str){for(int i=0;str[i];++i)putch(str[i]);return*this;}}qcout(Fout);
}using namespace IO;
#define rint register int
using ll=long long;using ull=unsigned long long;
using db = double;using ldb = long double;
#define vec vector
#define eb emplace_back
#define N 50001
#define mod 201314
__int128_t base = 1;
template<class T>
inline T Mod(T x){return x-mod*(base*x>>64);}
vec<int> e[N];
int n,m,cq;
int siz[N],son[N],fa[N],c[N],sc[N],ss[N],lc[N],rc[N],ans[N];
int tag[N],sum[N];
struct node{int id,x,z;bool sgn;}q[N<<1];
void dfs1(rint x){
siz[x] = 1;
for(int y:e[x]){
if(y == fa[x]) continue;
fa[y] = x;dfs1(y);siz[x] += siz[y];
if(!son[x] || siz[son[x]] < siz[y]) son[x] = y;
}
}
int buildc(rint ql,rint qr){
rint l = ql,r = qr,pos = 0,len = (sc[qr] - sc[ql]);
while(l <= r){
rint mid = (l + r) >> 1;
if(2*(sc[mid]-sc[ql]) <= len) pos = mid,l = mid + 1;
else r = mid - 1;
}
rint x = c[pos];ss[x] = qr-ql;
if(ql < pos) fa[lc[x] = buildc(ql,pos)] = x;
if(pos + 1 < qr) fa[rc[x] = buildc(pos+1,qr)] = x;
return x;
}
int build(rint x){
rint y = x;
do for(int v:e[y]) if(v ^ son[y]) fa[build(v)] = y; while(y = son[y]);
y = 0;
do c[y++] = x,sc[y] = sc[y-1] + siz[x] - siz[son[x]];while(x = son[x]);
return buildc(0,y);
}
inline void upd(rint x){
bool flag = true;rint val = 0;
while(x){
sum[x] += val;
if(flag){
tag[x]++;
if(rc[x]) tag[rc[x]]--;
val += 1 + ss[lc[x]];
sum[x] -= ss[rc[x]];
}
flag = (x ^ lc[fa[x]]);
if(flag && (x ^ rc[fa[x]])) val = 0;
x = fa[x];
}
}
inline int qry(rint x){
rint res = 0,val = 0;bool flag = true;
while(x){
if(flag){
res += sum[x] - sum[rc[x]];
res -= ss[rc[x]]*tag[rc[x]];
val += 1 + ss[lc[x]];
}
res += val*tag[x];
flag = (x ^ lc[fa[x]]);
if(flag && (x ^ rc[fa[x]])) val = 0;
x = fa[x];
}
return res;
}
inline void solve(){
base = (base<<64)/mod;
qcin>>n>>m;
rint f,l,r,x;
rep(i,2,n,1){qcin>>f;f++;e[f].eb(i);}
rep(i,1,m,1){
qcin>>l>>r>>x;r++;x++;
if(l) q[++cq] = {i,l,x,0};
q[++cq] = {i,r,x,1};
}
dfs1(1);rep(i,1,n,1) fa[i] = 0;build(1);
int now = 0;
sort(q+1,q+1+cq,[](node x,node y){return x.x<y.x;});
rep(i,1,cq,1){
while(now < q[i].x) now++,upd(now);
if(q[i].sgn) ans[q[i].id] += qry(q[i].z);
else ans[q[i].id] -= qry(q[i].z);
}
rep(i,1,m,1) qcout<<Mod(ans[i])<<'\n';
}
signed main(){
// cin.tie(nullptr)->sync_with_stdio(false);
solve();
}