```
#include<bits/stdc++.h>
using namespace std;
const long long MAXN=50010;
typedef long long ll;
struct edge{
long long next,to;
}e[MAXN*2];
struct linetree{
long long l,r,sum,lazy;
}tree[MAXN*4];
ll N,M,R,P,value[MAXN],eN;
long long head[MAXN],fa[MAXN],d[MAXN],son[MAXN],size[MAXN];
long long cnt,top[MAXN],id[MAXN],rk[MAXN],otpt[MAXN];
struct node{
long long l,r,z,id;
}qyl[50010],qyr[50010];
void insert(long long a1,long long a2) {
eN++;
e[eN].next=head[a1];
e[eN].to=a2;
head[a1]=eN;
}
void dfs1(long long now,long long deep,long long f) {
fa[now]=f;
d[now]=deep;
size[now]=1;
for(long long i=head[now];i;i=e[i].next) {
long long to=e[i].to;
if(to!=fa[now]) {
dfs1(to,deep+1,now);
size[now]+=size[to];
if(son[now]==0||size[to]>size[son[now]]) son[now]=to;
}
}
}
void dfs2(long long now,long long tp) {
cnt++;
id[now]=cnt;
rk[cnt]=now;
top[now]=tp;
if(son[now]) dfs2(son[now],tp);
for(long long i=head[now];i;i=e[i].next) {
long long to=e[i].to;
if(to!=fa[now]&&to!=son[now]) dfs2(to,to);
}
}
void pushdown(long long k) {
tree[2*k].lazy=(tree[2*k].lazy+tree[k].lazy)%P;
tree[2*k+1].lazy=(tree[2*k+1].lazy+tree[k].lazy)%P;
tree[2*k].sum=(tree[2*k].sum+(tree[2*k].r-tree[2*k].l+1)*tree[k].lazy)%P;
tree[2*k+1].sum=(tree[2*k+1].sum+(tree[2*k+1].r-tree[2*k+1].l+1)*tree[k].lazy)%P;
tree[k].lazy=0;
}
void build(long long k,long long l,long long r) {
tree[k].l=l,tree[k].r=r;
if(l==r) {
tree[k].sum=value[rk[l]]%P;
return ;
}
long long mid=(l+r)/2;
build(2*k,l,mid),build(2*k+1,mid+1,r);
tree[k].sum=(tree[2*k].sum+tree[2*k+1].sum)%P;
}
ll query(long long k,long long l,long long r) {
if(l<=tree[k].l&&tree[k].r<=r) return tree[k].sum%P;
if(tree[k].lazy) pushdown(k);
long long mid=(tree[k].l+tree[k].r)/2;
if(r<=mid) return query(2*k,l,r)%P;
if(l>mid) return query(2*k+1,l,r)%P;
return (query(2*k,l,r)+query(2*k+1,l,r))%P;
}
void add(long long k,long long l,long long r,long long z) {
if(l<=tree[k].l&&tree[k].r<=r) {
tree[k].sum=(tree[k].sum+(tree[k].r-tree[k].l+1)*z)%P;
tree[k].lazy=(tree[k].lazy+z)%P;
return ;
}
if(tree[k].lazy) pushdown(k);
long long mid=(tree[k].l+tree[k].r)/2;
if(l<=mid) add(2*k,l,r,z);
if(r>mid) add(2*k+1,l,r,z);
tree[k].sum=(tree[2*k].sum+tree[2*k+1].sum)%P;
}
ll sum(long long x,long long y) {
ll s=0;
long long topx=top[x],topy=top[y];
while(topx!=topy) {
if(d[topx]>=d[topy]) {
s=(s+query(1,id[topx],id[x]))%P;
x=fa[topx],topx=top[x];
}
else {
s=(s+query(1,id[topy],id[y]))%P;
y=fa[topy],topy=top[y];
}
}
if(d[x]>=d[y]) s=(s+query(1,id[y],id[x]))%P;
else s=(s+query(1,id[x],id[y]))%P;
return s;
}
void noice(long long x,long long y,long long z) {
long long topx=top[x],topy=top[y];
while(topx!=topy) {
if(d[topx]>=d[topy]) {
add(1,id[topx],id[x],z);
x=fa[topx],topx=top[x];
}
else {
add(1,id[topy],id[y],z);
y=fa[topy],topy=top[y];
}
}
if(d[x]>=d[y]) add(1,id[y],id[x],z);
else add(1,id[x],id[y],z);
}
long long cmp1(node a1,node a2) {return a1.l<a2.l;}
long long cmp2(node a1,node a2) {return a1.r<a2.r;}
int main()
{
freopen("ac.txt","w",stdout);
cin>>N>>M;
P=201314;
for(long long i=2; i<=N; i++) {
long long a1;
cin>>a1;
a1++;
insert(a1,i);
insert(i,a1);
}
dfs1(1,1,1);
dfs2(1,1);
cnt=0;
build(1,1,N);
for(long long i=1; i<=M; i++) {
cin>>qyl[i].l>>qyl[i].r>>qyl[i].z;
qyl[i].r++,qyl[i].z++,qyl[i].id=i;
qyr[i]=qyl[i];
}
sort(qyl+1,qyl+M+1,cmp1);
sort(qyr+1,qyr+M+1,cmp2);
long long ll=1,rr=1;
for(long long i=1; i<=N; i++) {
noice(1,i,1);
while(qyl[ll].l==i) otpt[qyl[ll].id]=
(otpt[qyl[ll].id]+P-sum(1,qyl[ll].z)%P)%P,ll++;
while(qyr[rr].r==i) otpt[qyr[rr].id]=
(otpt[qyr[rr].id]+P+sum(1,qyr[rr].z)%P)%P,rr++;
}
for(long long i=1; i<=M; i++) cout<<otpt[i]<<endl;
return 0;
}
```
修改了一下，链查询时的模改好了，但还是0pt
by LinkyChristian @ 2021-10-16 11:38:57
~~红名蓝钩の萌新~~
by DYYqwq @ 2022-09-20 19:59:42