OI

AHSDFZ 20170301 树 (tree.pas/c/cpp)

Description

给你一棵树，点带权，且以点 1 为根。有这么一个游戏：从根开始，每次拿出一个点，然后在它和它的所有儿子中随机选择一个点(每个点的概率相同)。若

这个点是当前拿出的点，游戏结束且你获得其点权的分数；否则拿出该点，然后重复上述过程。

现在你要算出这个游戏的期望得分，而且要满足两个操作：

操作 1：修改某个点的权值。

操作 2：将某个节点为根的子树转移到另一个节点的下方。

Input

输入文件为 tree.in。

输入数据第一行包含一个数 n,m，表示点的个数和操作个数。

第二行包含 n 个整数，表示每个点的点权。

接下来 n 行每行两个数，表示一条树边的两个端点。

在接下来 m 行每行 3 个数字 type,x,y。表示一个操作。若 type=0，则表示将点 x 的权值修改成 y；否则表示将 x 为根的子树转移到 y 下方。(若 y 是 x 的后辈，则视为没有操作。)

Output

输出文件为 tree.out。

对于每次操作，都输出操作过后进行游戏的期望得分。注意：为了防止精度误差，这里将答案对 10^9+7 取模，并把除法看成是乘逆元。

Sample Input

1
2
3
4
5
6
7
8
9

5 3
2 3 3 4 4
1 2
1 3
2 4
2 5
0 3 1
1 2 3
1 5 3

Sample Output

1
2
3

222222226
166666670
416666672

HINT

对于 30%的数据，n,m<=1000。

对于 100%的数据，n,m<=200000。

Source

AHSDFZ

Solution

Splay维护DFS序。

首先如果没有0,1操作，答案就是 \( \sum_i (a_i * \prod_j c_j) \) , 其中c_i表示i节点的度数，特殊的，如果i=1，则表示1的度数+1。

这个式子表示了每个点对答案贡献乘概率。

于是我们用splay维护dfs序，每个点维护子树和，答案就是sum[root]，这里的root为splay的根而不是1。

0操作很好做，1操作在移动子树的时候需要去掉以前的父亲对子树贡献还要加上新父亲对子树贡献。

因为维护的是子树sum，因此在下传乘法标记的时候sum也要更新。

这题有两个坑点：

  • a[i]可以为0。这也就导致了我们必须维护 \( \prod_j c_j \) 。否则因为无法求出0的逆元而导致WA。
  • 在操作“1 x y”时，y可能为x以前的父亲，所以我们在计算该操作对两个父亲贡献的时候，要及时更新c。

Code

  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
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn = 400009;
typedef long long LL;
const LL P = 1000000007ll;
vector<int> son[maxn];
LL a[maxn], c[maxn];
int fa[maxn], dfn[maxn], efn[maxn], clo = 1, n, m;
inline int getint() {
    int r = 0; bool b = true; char c = getchar();
    while ('0' > c || c > '9') { if (c == '-') b = false; c = getchar(); }
    while ('0' <= c && c <= '9') { r = r * 10 + (c - '0'); c = getchar(); }
    if (b) return r;
    return -r;
}
LL ksm(LL a, LL b, LL c) {
    LL r = 1ll, t = a;
    while (b) {
        if (b & 1ll) r = (r * t) % c;
        t = (t * t) % c;
        b >>= 1ll;
    }
    return r;
}
LL niyuan(LL x) { return ksm(x, P-2ll, P); }
namespace splay {
    int c[maxn][2], fa[maxn], sta[maxn], siz[maxn], tail;
    LL tag[maxn], sum[maxn], val[maxn], dep[maxn], tag2[maxn];
    void pushup(int x) {
        sum[x] = (sum[c[x][0]] + sum[c[x][1]] + val[x]) % P;
        siz[x] = siz[c[x][0]] + siz[c[x][1]] + 1;
    }
    void mul(int x, LL v) {
        tag[x] = (tag[x] * v) % P;
        val[x] = (val[x] * v) % P;
        sum[x] = (sum[x] * v) % P;
    }
    void mul2(int x, LL v) {
        tag2[x] = tag2[x] * v % P;
        dep[x] = dep[x] * v % P;
    }
    void pushdown(int x) {
        if (c[x][0]) { mul(c[x][0], tag[x]); mul2(c[x][0], tag2[x]); }
        if (c[x][1]) { mul(c[x][1], tag[x]); mul2(c[x][1], tag2[x]); }
        tag[x] = tag2[x] = 1;
    }
    void rotate(int x) {
        int y = fa[x], z = fa[y], a = c[y][1] == x, b = a ^ 1;
        if (z) c[z][c[z][1]==y] = x;
        fa[x] = z; fa[y] = x; if (c[x][b]) fa[c[x][b]] = y;
        c[y][a] = c[x][b]; c[x][b] = y;
        pushup(y); pushup(x);
    }
    void splay(int x, int pos) {
        int y;
        for (y = x; y; y = fa[y]) sta[++tail] = y;
        while (tail) pushdown(sta[tail--]);
        while (fa[x] != pos) {
            y = fa[x];
            if (fa[y] != pos) {
                if (c[y][0] == x ^ c[fa[y]][0] == y) rotate(x);
                else rotate(y);
            }
            rotate(x);
        }
    }
    int pre(int x) {
        splay(x, 0);
        x = c[x][0];
        while (c[x][1]) x = c[x][1];
        return x;
    }
    int suc(int x) {
        splay(x, 0);
        x = c[x][1];
        while (c[x][0]) x = c[x][0];
        return x;
    }
    int Ord(int x) {
        splay(x, 0);
        return siz[c[x][0]];
    }
    bool is_anc(int x, int y) {
        return Ord(dfn[x]) <= Ord(dfn[y]) && Ord(efn[y]) <= Ord(efn[x]);
    }
    int split(int i) {
        int x = pre(dfn[i]), y = suc(efn[i]);
        splay(x, 0); splay(y, x);
        pushdown(x); pushdown(y);
        int ret = c[y][0]; c[y][0] = 0; fa[ret] = 0;
        pushup(y); pushup(x);
        return ret;
    }
    void modify(int x, LL v) {
        int pos = dfn[x];
        splay(pos, 0);
        val[pos] = (val[pos] * v) % P;
        pushup(pos);
    }
    LL query(int x) {
        x = dfn[x];
        splay(x, 0);
        return dep[x];
    }
    void modify_tree(int x, LL v) {
        splay(x, 0);
        mul(x, v); mul2(x, v);
    }
    void modify_tree2(int x, LL v) {
        int l = pre(dfn[x]), r = suc(efn[x]);
        splay(l, 0); splay(r, l);
        if (c[r][0]) { mul(c[r][0], v); mul2(c[r][0], v); }
        pushup(r); pushup(l);
    }
    void insert_tree(int x, int y) {
        int l = dfn[y], r = suc(l);
        splay(l, 0); splay(r, l);
        pushdown(l); pushdown(r);
        c[r][0] = x; fa[x] = r;
        pushup(r); pushup(l);
    }
    void qinding(int x, LL v) {
        x = dfn[x];
        splay(x, 0);
        val[x] = v;
        pushup(x);
    }
}
void dfs(int now, int father) {
    dfn[now] = ++clo;
    fa[now] = father;
    c[now] = 1;
    for (auto &v : son[now]) if (v != father) { dfs(v, now); ++c[now]; }
    efn[now] = ++clo;
}
void dfs2(int now, LL dis) {
    dis = (dis * niyuan(c[now])) % P;
    splay::val[dfn[now]] = (dis * a[now]) % P;
    splay::dep[dfn[now]] = dis;
    for (auto &v : son[now]) if (v != fa[now]) dfs2(v, dis);
}
int main() {
    freopen("tree.in", "r", stdin);
    freopen("tree.out", "w", stdout);
    int x, y, z;
    n = getint(); m = getint();
    for (int i = 1; i <= n; ++i) a[i] = getint();
    for (int i = 1; i < n; ++i) {
        x = getint(); y = getint();
        son[x].push_back(y); son[y].push_back(x);
    }
    dfs(1, 0);
    dfs2(1, 1ll);
    splay::tag[clo + 1] = splay::tag2[clo + 1] = 1;
    splay::pushup(clo + 1);
    for (int i = clo; i >= 1; --i) {
        splay::c[i][1] = i + 1;
        splay::pushup(i);
        splay::fa[i + 1] = i;
        splay::tag[i] = splay::tag2[i] = 1;
    }
    for (int i = 1; i <= m; ++i) {
        z = getint(); x = getint(); y = getint();
        if (z == 0) {
            splay::qinding(x, splay::query(x) * LL(y) % P);
            a[x] = y;
        }
        else {
            if (!splay::is_anc(x, y)) {
                z = splay::split(x);
                splay::modify_tree(z, niyuan(splay::query(fa[x])));
                splay::modify_tree2(fa[x], c[fa[x]] * niyuan(c[fa[x]] - 1) % P);
                --c[fa[x]];
                splay::modify_tree2(y, c[y] * niyuan(c[y] + 1) % P);
                splay::modify_tree(z, splay::query(y));
                splay::insert_tree(z, y);
                ++c[y]; fa[x] = y;
            }
        }
        splay::splay(1, 0);
        printf("%lld\n", splay::sum[1]);
    }
}