Codeforces Round #336 (Div. 1) D. Power Tree（dfs序线段树）

题意：

思路：

     首先，直接模拟很不现实，只能先离线，造出空树，再慢慢更新树
     那么现在想一下怎么维护这颗树，首先，我们算每个点对根节点的贡献，发现每个点的贡献可以表示为$v_i*sz_1*sz_2*...*$(其中sz1,sz2是这个点和根节点的路径上的点，这些点的直接儿子)，只要我们新加入一个节点，假设父亲的直接儿子节点个数为sz，那么这次修改就是把它父亲的这颗子树中的所有节点的贡献乘以$\frac{sz+1}{sz}$。
     然后是查询，如果我们直接查询根，那我们只要把所有点的贡献加起来就行了，可是如果不是根，那我们把他的子树的贡献和处以他父亲的倍率（可以从上面的公式看出来）
    这样，我们就可以把所有操作限定在子树里面了， 说到了子树，那么就应该是dfs序线段树了，这样，我们维护一个sum，一个倍率，每次加点就把该点的父亲的子树都改变一次贡献（sum和倍率都改），查询就找出sum，并除以父亲的倍率即可。
     因为要取模，记得用逆元

错误及反思：

     居然有个地方写了个fa[fa[Q[i].poi]]。。。

代码：

#include<bits/stdc++.h>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const int N = 200100;
const long long mod =1000000007;

long long segtree[N<<2],bl[N<<2],lazy[N<<2];
int fa[N],val[N],now=1,id[N],to[N],tot=2,q,sz[N];

struct ope{
    int xz,poi;
};
vector<ope> Q;
vector<int> son[N];

void dfs(int node){
    id[node]=now++;
    for(int i=0;i<son[node].size();i++)
        dfs(son[node][i]);
    to[node]=now-1;
}

long long pow_mod(long long a,long long b){
    long long ret = 1;
    while(b){
        if(b & 1) ret = (ret * a) % mod;
        a = (a * a) % mod;
        b >>= 1;
    }
    return ret;
}

long long Fermat(long long a){return pow_mod(a, mod-2);}

void chang(long long &a,long long b){
    a*=b;
    a%=mod;
}
void pushdown(int l,int r,int rt){
    if(lazy[rt]!=1){
        chang(segtree[rt<<1],lazy[rt]);
        chang(segtree[rt<<1|1],lazy[rt]);
        chang(lazy[rt<<1],lazy[rt]);
        chang(lazy[rt<<1|1],lazy[rt]);
        chang(bl[rt<<1],lazy[rt]);
        chang(bl[rt<<1|1],lazy[rt]);
        lazy[rt]=1;
    }
}
void pushup(int l,int r,int rt){
    segtree[rt]=segtree[rt<<1]+segtree[rt<<1|1];
    segtree[rt]%=mod;
}
void build(int l,int r,int rt){
    if(l==r){
        bl[rt]=1;
        lazy[rt]=1;
        if(l==1) segtree[rt]=val[1];
        else segtree[rt]=0;
        return ;
    }
    int m=(l+r)/2;
    build(lson);
    build(rson);
    bl[rt]=1;
    lazy[rt]=1;
    pushup(l,r,rt);
}


void add(int L,int R,long long v,long long w,int l,int r,int rt){
    if(L<=l&&R>=r){
        chang(bl[rt],v);
        chang(bl[rt],w);
        chang(lazy[rt],v);
        chang(lazy[rt],w);
        chang(segtree[rt],v);
        chang(segtree[rt],w);
        return ;
    }
    pushdown(l,r,rt);
    int m=(l+r)/2;
    if(L<=m) add(L,R,v,w,lson);
    if(R>m) add(L,R,v,w,rson);
    pushup(l,r,rt);
}

void update(int p,int v,int l,int r,int rt)
{
    if(l==r)
    {
        segtree[rt]=v*bl[rt];
        segtree[rt]%=mod;
        return ;
    }
    pushdown(l,r,rt);
    int m=(l+r)/2;
    if(p<=m) update(p,v,lson);
    else update(p,v,rson);
    pushup(l,r,rt);
}
long long querybl(int p,int l,int r,int rt){
    if(l==r)
        return bl[rt];
    pushdown(l,r,rt);
    int m=(l+r)/2;
    long long ans=0;
    if(p<=m) ans=querybl(p,lson);
    else ans=querybl(p,rson);
    pushup(l,r,rt);
    return ans;
}
long long query(int L,int R,int l,int r,int rt){
    if(L<=l&&R>=r){
        return segtree[rt];
    }
    pushdown(l,r,rt);
    int m=(l+r)/2;
    long long ans=0;
    if(L<=m) ans+=query(L,R,lson);
    if(R>m) ans+=query(L,R,rson);
    pushup(l,r,rt);
    ans%=mod;
    return ans;
}
int main(){
    scanf("%d%d",&val[1],&q);
    while(q--){
        int ta,tb,tc;
        scanf("%d",&ta);
        if(ta==1){
            scanf("%d%d",&tb,&tc);
            son[tb].push_back(tot);
            fa[tot]=tb;
            val[tot]=tc;
            Q.push_back({1,tot++});
        }
        else{
            scanf("%d",&tb);
            Q.push_back({2,tb});
        }
    }
    fa[1]=1;
    sz[1]=1;
    tot--;
    dfs(1);
    build(1,tot,1);

    for(int i=0;i<Q.size();i++)
    {
        if(Q[i].xz==1){
            int faq=fa[Q[i].poi];
            long long ny=Fermat(sz[faq]);
            update(id[Q[i].poi],val[Q[i].poi],1,tot,1);
            add(id[faq],to[faq],ny,sz[faq]+1,1,tot,1);
            sz[faq]++;
            sz[Q[i].poi]++;
        }
        else{
            long long ny;
            if(Q[i].poi==1) ny=1;
            else ny=Fermat(querybl(id[fa[Q[i].poi]],1,tot,1));
            long long ans=query(id[Q[i].poi],to[Q[i].poi],1,tot,1);
            chang(ans,ny);

            printf("%lld\n",ans);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170