数据结构懒标记时间戳差异问题

对于数据结构打 lazytag 后节点时空不统一问题的解决

可以看看之前写的一篇文章 线段树初步理解 ，里头初步介绍了懒标记的作用与使用懒标记所带来的时空不统一的问题。实际上是可以将懒标记拓展到其他数据结构上的。

就以经典的 毛毛虫链剖分 举例子，就是现在我要给树上的与给定的两个点之间路径所经过的所有点相连接边先乘以 \(x\) 然后再给经过的边加上 \(y\) ，由于这这两步操作并没有结合律，因此我不能合并操作，利用之前 NOI2021 d1t1 的技巧，我轻重链剖分后需要维护轻边，那么我把对轻边的影响直接记在轻边的父点上，这样一次性可以改一坨轻边。
这里就十分像线段树了，就相当于一个点管了很多个轻边，而对这一坨轻边的修改本质上就是相当于在这个点上打 tag ，然后就会遇到一个问题，就是我询问单点的时候我不知道每个点同步到父亲的哪一个历史状态（也有可能是现在状态），因此我就需要给每个轻边维护一个 tag 表示同步到其父点的那个历史版本，然后询问到轻边的时候就需要对着父点的 tag 来更新自己的状态就行了。
然后遇到了问题，我可能遇到乘以 0 的操作，因此我需要在多维护一个上一次修改成 0 的时间戳是什么时候，这就有点像历史断代一样，那么现在就有 大历史 和 小历史 ， 小历史 在 大历史 里面，然后乘以某个数就是推进 小历史 ，而乘以 0 就是换 大历史。你大概就是在每个点被访问的时候同步历史即可。

自己弄的定理：
在更新历史的时候，如果一个节点的历史比其父点更加先进，那么可以无视父点的操作，儿子的历史状态会改变当且仅当其被父点更新

#include <bits/stdc++.h>
#define int long long
#define pb push_back
using namespace std;
inline int read(){
	int x=0,f=1;char ch=getchar();
	while(!isdigit(ch))f^=ch=='-',ch=getchar();
	while(isdigit(ch))x=x*10+(ch^48),ch=getchar();
	return f?x:-x;
}
const int N=1e5+5,mo=1e9+7;
void red(int &x){(x>=mo)?(x-=mo):1;}
inline int qpow(int x,int t){
    int ret=1;
    for(;t;t>>=1,x=x*x%mo)if(t&1)ret=ret*x%mo;
    return ret;
}
int dep[N],top[N],up[N],siz[N],son[N],dfn[N],dfntot,n,m,last[N],cnt[N],E[N],ans1,ans2;
vector<int> G[N];
void dfs1(int u,int fa){
	dep[u]=dep[up[u]=fa]+1;
	siz[u]=1;
	for(int v:G[u])if(v!=fa){
		dfs1(v,u);
		siz[u]+=siz[v];
		if(siz[v]>siz[son[u]])son[u]=v;
	}
}
void dfs2(int u,int tp){
	dfn[u]=++dfntot;
	top[u]=tp;
	if(son[u])dfs2(son[u],tp);
	for(int v:G[u])if(v!=son[u]&&v!=up[u]){
		cnt[v]=1;
		dfs2(v,v);
	}
}
struct SegmentTree{
    #define lc p<<1
    #define rc p<<1|1
    #define mid (l+r>>1)
	int val[N<<2],add[N<<2],mul[N<<2];
    void build(int p,int l,int r){
        val[p]=add[p]=0;
        mul[p]=1;
        if(l==r)return;
        build(lc,l,mid);
        build(rc,mid+1,r);
    }
	void pushdown(int p,int l,int r){
		mul[lc]=mul[lc]*mul[p]%mo;
        mul[rc]=mul[rc]*mul[p]%mo;
        add[lc]=add[lc]*mul[p]%mo;
        add[rc]=add[rc]*mul[p]%mo;
        val[lc]=val[lc]*mul[p]%mo;
        val[rc]=val[rc]*mul[p]%mo;
        mul[p]=1;
        red(add[lc]+=add[p]);
        red(add[rc]+=add[p]);
        red(val[lc]+=add[p]*(mid-l+1)%mo);
        red(val[rc]+=add[p]*(r-mid)%mo);
        add[p]=0;
    }
    void modify1(int p,int l,int r,int L,int R,int d){
        if(L<=l&&r<=R){
            mul[p]=mul[p]*d%mo;
            add[p]=add[p]*d%mo;
            val[p]=val[p]*d%mo;
            return;
        }
        pushdown(p,l,r);
        if(L<=mid)modify1(lc,l,mid,L,R,d);
        if(mid<R)modify1(rc,mid+1,r,L,R,d);
    }
    void modify2(int p,int l,int r,int L,int R,int d){
        if(L<=l&&r<=R){
            red(add[p]+=d);
            red(val[p]+=d*(r-l+1)%mo);
            return;
        }
        pushdown(p,l,r);
        if(L<=mid)modify2(lc,l,mid,L,R,d);
        if(mid<R)modify2(rc,mid+1,r,L,R,d);
    }
    void modify3(int p,int l,int r,int L,int R,int d){
        modify1(1,1,n,L,R,0);
        modify2(1,1,n,L,R,d);
    }
    int query(int p,int l,int r,int x){
        if(l==r)return val[p];
        pushdown(p,l,r);
        if(x<=mid)return query(lc,l,mid,x);
        else return query(rc,mid+1,r,x);
    }
    #undef lc
    #undef rc
    #undef mid
}T1,T2,T3;
/*
T1维护重链上的边，每条边被其父点统计
T2维护每个节点上一次清零的时间戳
T3维护每个节点上一次清零开始整体乘的乘积
每个jump边被其父点统计
cnt表示记录上一次清零开始后的jump被父亲影响的lazytag
*/
int update(int x){
    int t=T2.query(1,1,n,dfn[up[x]]);
    if(last[x]<t){
        E[x]=0;
        last[x]=t;
        cnt[x]=T3.query(1,1,n,dfn[up[x]]);
        return 0;
    }
    else if(last[x]==t){
        int hv=T3.query(1,1,n,dfn[up[x]])*qpow(cnt[x],mo-2)%mo;
        cnt[x]=cnt[x]*hv%mo;
        E[x]=E[x]*hv%mo;
        return 0;
    }
    else return 1;
}
void mdf(int x,int y,int c,int p,int tms){
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]])swap(x,y);
        if(x!=top[x]){
            T1.modify1(1,1,n,dfn[top[x]],dfn[up[x]],(1+mo-p)%mo);
            T1.modify2(1,1,n,dfn[top[x]],dfn[up[x]],p*c%mo);
        }
        if(son[x]){
            T1.modify1(1,1,n,dfn[x],dfn[x],(1+mo-p)%mo);
        }
        if(p==1){
            T2.modify3(1,1,n,dfn[top[x]],dfn[x],tms);
            T3.modify3(1,1,n,dfn[top[x]],dfn[x],1);
            E[top[x]]=c;
            cnt[top[x]]=1;
            last[top[x]]=tms;
        }
        else{
            T3.modify1(1,1,n,dfn[top[x]],dfn[x],(1+mo-p)%mo);
            int t=update(top[x]);
            E[top[x]]=E[top[x]]*(1+mo-p)%mo;
            red(E[top[x]]+=p*c%mo);
            if(!t)cnt[top[x]]=cnt[top[x]]*(1+mo-p)%mo;
        }
        x=up[top[x]];
    }
    if(dep[x]>dep[y])swap(x,y);
    if(x!=y){
        T1.modify1(1,1,n,dfn[x],dfn[up[y]],(1+mo-p)%mo);
        T1.modify2(1,1,n,dfn[x],dfn[up[y]],p*c%mo);
    }
    if(son[y])T1.modify1(1,1,n,dfn[y],dfn[y],(1+mo-p)%mo);
    if(x!=top[x]){
        T1.modify1(1,1,n,dfn[up[x]],dfn[up[x]],(1+mo-p)%mo);
    }
    if(p==1){
        T2.modify3(1,1,n,dfn[x],dfn[y],tms);
        T3.modify3(1,1,n,dfn[x],dfn[y],1);
        if(x==top[x]){
            last[top[x]]=tms;
            E[top[x]]=0;
            cnt[top[x]]=1;
        }
    }
    else{
        T3.modify1(1,1,n,dfn[x],dfn[y],(1+mo-p)%mo);
        if(x==top[x]){
            if(x!=1){
                update(top[x]);
                E[top[x]]=E[top[x]]*(1+mo-p)%mo;
            }
        }
    }
}
void dfs3(int u){
    if(son[u]){
    	int e=T1.query(1,1,n,dfn[u]);
        red(ans1+=e);
        red(ans2+=e*son[u]%mo);
        dfs3(son[u]);
    }
    for(int v:G[u])if(v!=up[u]&&v!=son[u]){
        int t=update(v);
        red(ans1+=E[v]);
        red(ans2+=E[v]*v%mo);
        dfs3(v);
    }
}
signed main(){
//	freopen("lkkts.in","r",stdin);
    n=read(),m=read();
    for(int i=2;i<=n;++i){
        int x=read();
        G[x].pb(i);
        G[i].pb(x);
    }
    dfs1(1,0);
    dfs2(1,1);
    T1.build(1,1,n);
    T2.build(1,1,n);
    T3.build(1,1,n);
    T3.modify3(1,1,n,1,n,1);
    for(int i=1;i<=m;++i){
        int x=read(),c=read(),p=read();
        mdf(1,x,c,p,i);
    }
    dfs3(1);
    printf("%lld\n%lld\n",ans1,ans2);
}