#include<bits/stdc++.h> #define LL long long #define pii pair<LL,int> #define mem(a,b) memset(a,b,sizeof(a)) using namespace std; const int maxn=5e4+5; const int inf=0x3f3f3f3f; const int MOD=201314; struct node{ int nm,z,id; bool f; }p[maxn<<1]; struct TMD{ int to,next; }edge[maxn<<1]; int head[maxn],cnt,knt,n,m,deep[maxn],f[maxn],ans[maxn]; int top[maxn],sz[maxn],sn[maxn],tree[maxn],pre[maxn]; int sum[maxn<<2],lazy[maxn<<2]; bool cmp(node A,node B){return A.nm<B.nm;} void add(int from,int to){ edge[++cnt]={to,head[from]}; head[from]=cnt; } void dfs1(int now,int fa){ deep[now]=deep[fa]+1; sz[now]=1;f[now]=fa; for(int i=head[now];i;i=edge[i].next){ int to=edge[i].to; if(to==fa) continue; dfs1(to,now); sz[now]+=sz[to]; if(!sn[now]||sz[sn[now]]<sz[to]) sn[now]=to; } } void dfs2(int now,int fa,int tp){ tree[now]=++knt;pre[knt]=now;top[now]=tp; if(!sn[now]) return ; dfs2(sn[now],now,tp); for(int i=head[now];i;i=edge[i].next){ int to=edge[i].to; if(to==fa||to==sn[now]) continue; dfs2(to,now,to); } } void pushdown(int l,int r,int rt){ int mid=(l+r)>>1; if(lazy[rt]){ lazy[rt<<1]=(lazy[rt<<1]+lazy[rt])%MOD; lazy[rt<<1|1]=(lazy[rt<<1|1]+lazy[rt])%MOD; sum[rt<<1]=(sum[rt<<1]+lazy[rt]*(mid-l+1)%MOD)%MOD; sum[rt<<1|1]=(lazy[rt<<1|1]+lazy[rt]*(r-mid)%MOD)%MOD; lazy[rt]=0; } } void modify(int L,int R,int l,int r,int rt,int k){ if(L<=l&&R>=r){ lazy[rt]=(lazy[rt]+k)%MOD; sum[rt]=(sum[rt]+(r-l+1)*k)%MOD;return ; } pushdown(l,r,rt); int mid=(l+r)>>1; if(L<=mid) modify(L,R,l,mid,rt<<1,k); if(R>mid) modify(L,R,mid+1,r,rt<<1|1,k); sum[rt]=sum[rt<<1]+sum[rt<<1|1]; } void get_modify(int x,int y){ int f1=top[x],f2=top[y]; while(f1!=f2){ if(deep[f1]<deep[f2]) swap(f1,f2),swap(x,y); modify(tree[f1],tree[x],1,n,1,1); x=f[f1],f1=top[x]; } if(deep[x]<deep[y]) swap(x,y); modify(tree[y],tree[x],1,n,1,1); } int dfs_sum(int L,int R,int l,int r,int rt){ if(L<=l&&R>=r) return sum[rt]; pushdown(l,r,rt); int mid=(l+r)>>1,ant=0; if(L<=mid) ant=(ant+dfs_sum(L,R,l,mid,rt<<1))%MOD; if(R>mid) ant=(ant+dfs_sum(L,R,mid+1,r,rt<<1|1))%MOD; return ant; } int get_sum(int x,int y){ int f1=top[x],f2=top[y]; int ant=0; while(f1!=f2){ if(deep[f1]<deep[f2]) swap(f1,f2),swap(x,y); ant=(ant+dfs_sum(tree[f1],tree[x],1,n,1))%MOD; x=f[f1],f1=top[x]; } if(deep[x]<deep[y]) swap(x,y); ant=(ant+dfs_sum(tree[y],tree[x],1,n,1))%MOD; return ant; } int main(){ int u,v,w; scanf("%d%d",&n,&m); for(int i=2;i<=n;i++){ scanf("%d",&u);++u; add(u,i); } for(int i=1;i<=m;i++){ scanf("%d%d%d",&u,&v,&w); ++u;++v;++w; p[2*i-1]={u-1,w,i,false}; p[2*i]={v,w,i,true}; } sort(p+1,p+2*m+1,cmp); dfs1(1,0); dfs2(1,0,1); int id=1; for(int i=1;i<=2*m;i++){ while(id<=p[i].nm) get_modify(1,id++); if(p[i].f){ ans[p[i].id]=(ans[p[i].id]+get_sum(1,p[i].z)+MOD)%MOD; }else{ ans[p[i].id]-=get_sum(1,p[i].z); } } for(int i=1;i<=m;i++){ printf("%d\n",ans[i]); } return 0; }
全部评论
(0) 回帖