题解 CF607D 【Power Tree】

· · 题解

题意:给你一些操作,其中一个操作是加入一个点,另一个操作是查询一个点的贡献.

对于一个点,它的贡献为:|S|*\sum_{d \in s}d

其中S是它的权值w_i与它的儿子 (不是子树) 的可重集合.

考虑如何维护.

当加入一个点i时,它只会让它的父亲的|S|加一,并且对包含它的祖先产生w_i的贡献.

我们可以想到,维护dfs序,并用线段树维护权值.

那么如何维护呢.

我们发现如果我们将f(i)视为query(d[i],d[i]+sz[i]-1) 的话,当加入一个点时,它的父亲的|S|会变成|S|+1,所以我们将d[f]+sz[f]-1区间除上|S|再乘上|S|+1,就不会出错.,但此时加入的点权不能设成w_i了,需要设成w_i * query(d[f],d[f])/w[f] .这么做是因为你需要维护总体的和.在查询时我们再除上query(d[f],d[f])/w[f]就行了.至于不单纯乘上s_f的原因,是因为你的祖先也对你进行了乘法操作,如果你单纯的去乘s_f的话那么贡献就不对了.

代码:

#include<bits/stdc++.h>
using namespace std;
#define ls (i<<1)
#define rs (i<<1|1)
#define mid ((l+r)>>1)
#define rep(i,j,k) for(int i=(j);i<=(k);i++)
#define ll long long
const int N=1514514;
const int mod=1e9+7;
vector<int> v[N],q[N];
int fa[N],sz[N],d[N];
int n,m,pos,as[N];
ll tr[N],s[N],lz[N],w[N];
ll msk(ll a){ll b=mod-2,k=1;
    while(b){if(b&1)k=k*a%mod;a=a*a%mod;b>>=1;}return k;
}
void down(int i){
    ll k=lz[i];lz[i]=1;if(k<=1)return;
    lz[ls]=lz[ls]*k%mod;lz[rs]=lz[rs]*k%mod;
    tr[ls]=tr[ls]*k%mod;tr[rs]=tr[rs]*k%mod;
}
void add(int i,int l,int r,int s,int t,ll w1,ll w2){
    if(s<=l&&r<=t){tr[i]=(tr[i]+w1)*w2%mod;lz[i]=lz[i]*w2%mod;return;}
    down(i);if(s<=mid)add(ls,l,mid,s,t,w1,w2);
    if(t>mid) add(rs,mid+1,r,s,t,w1,w2);tr[i]=(tr[ls]+tr[rs])%mod;
}//乘法和加法放一起了()
void dfs(int x){d[x]=++pos;sz[x]=1;
    for(int i=0;i<v[x].size();i++)
        dfs(v[x][i]),sz[x]+=sz[v[x][i]];
}ll query(int i,int l,int r,int s,int t){
    if(s<=l&&r<=t)return tr[i];down(i);
    ll ans=0;if(s<=mid)ans=query(ls,l,mid,s,t);
    if(t>mid)ans=(ans+query(rs,mid+1,r,s,t))%mod;return ans;
}
int main(){
    scanf("%d%d",&w[1],&m);n=1;
    for(int i=1,op,x;i<=m;i++){
        scanf("%d%d",&op,&x);
        if(op==1)n++,scanf("%d",&w[n]),fa[n]=x,v[x].push_back(n);
        else q[n].push_back(x);
    }dfs(1);add(1,1,n,1,1,w[1],1);s[1]=1;
    for(int j=0;j<q[1].size();j++)printf("%lld\n",w[1]);
    rep(i,2,n){int f=fa[i];
        add(1,1,n,d[f],d[f]+sz[f]-1,0,(s[f]+1)*msk(s[f])%mod);s[f]++;s[i]=1;
        add(1,1,n,d[i],d[i],query(1,1,n,d[f],d[f])*msk(w[f])%mod*w[i]%mod,1);
        //这里先乘再加与先加再乘没有区别
        for(int j=0;j<q[i].size();j++){
            int u=q[i][j];ll kkr=query(1,1,n,d[u],d[u]+sz[u]-1);
            if(u==1)printf("%lld\n",kkr);//特判1防止查询 0
            else printf("%lld\n",kkr*w[fa[u]]%mod*msk(query(1,1,n,d[fa[u]],d[fa[u]]))%mod);//记得除上自己乘的贡献数
        }
    }
}