Charged Tree

题意: 给定一棵有根带权树. 有两种操作下移和上移. 下移, 即每个节点将自己的权值均分给各个儿子, 假设叶子结点有一个无限长的儿子链, 即叶子结点每次下移都会把自己和整条儿子链下移一位. 每个节点的新值就是它从父亲得到的那个值 (他自己原来的值已经分给了儿子) , 特别地, 一次下移操作后根变成0. 上移, 即对每个节点, 将所有儿子的权值加起来赋给自己.

首先观察发现, 下移是不丢失信息的, 下移与上移相同次数会完美回到原来的状态. 有点像括号匹配, 若将下移作为左括号, 上移作为右括号, 那么匹配的括号序列等价于不存在.

如果没有加值操作, 可以做括号匹配, 剩下的一定是若干次上移紧接着若干次下移. 记上移$u$次, 下移$d$次. 那么上移的结果等价于, 将树上每个点的初值不加在自己, 而加在其$u$级父亲 (u级父亲 = (u == 0) ? 自己 : 父亲的(u-1)级父亲) 上. 然后再做下移, 每个点的最终答案等于其$d$级父亲的权值一路向下, 每经过一个节点, 就除以其儿子个数, 这可以在dfs过程中维护访问栈做到.

最后考虑加值操作. 可以认为现在已经没有实际上的上移操作, 他被等价变换为了赋初值操作. 加上加值操作后大致思路是不变的, 即: 希望在做完赋初值操作和放完所有加值请求之后, 通过一次dfs处理所有下传. 我们尝试将加值操作直接加在 “正确” 的位置上, “正确的位置” 是指, 希望只在这个位置放上一个加值请求和它应当下传到的层数, 而不是动态地让它跑来跑去. 手玩一下可以发现, 每次加值操作等价于加在——该结点日后会到达的最高的祖先——上 (若不会变的更高, 就加在自己身上) . 为了维护这个东西, 可以倒着遍历请求序列, 维护过程中最高点, 高出终点多少 (即从此下传多少层) 和高出加值请求处多少 (正确的位置是哪个祖先) .

AC代码

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
#include <bits/stdc++.h>
#define maxn 500005
#define MOD 1000000007LL
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
struct oper {
ll high, low, val;
};
vector<pll> downop[maxn];
ll levval[maxn], a[maxn], ans[maxn];
vector<ll> G[maxn];
vector<oper> up[maxn];
char type[maxn];
ll ind[maxn], val[maxn];
ll n;
ll inv[maxn];
vector<ll> path;
void dfsup(ll u, ll fa, ll lev) {
auto it = find(G[u].begin(), G[u].end(), fa);
if (it != G[u].end()) G[u].erase(it);
path.push_back(u);
for (auto p : up[u]) {
ll h = max(0LL, lev - p.high);
downop[path[h]].push_back(pll(p.low, p.val));
}
for (auto v : G[u]) {
dfsup(v, u, lev + 1);
}
path.pop_back();
}
ll mul = 1, divi = 1;
void dfsdown(ll u, ll lev) {
for (auto p : downop[u]) {
ll h = lev + p.first;
if (h < n) levval[h] = (levval[h] + p.second * mul) % MOD;
}
ans[u] = levval[lev] * divi % MOD;
for (auto v : G[u]) {
mul = mul * G[u].size() % MOD;
divi = divi * inv[G[u].size()] % MOD;
dfsdown(v, lev + 1);
mul = mul * inv[G[u].size()] % MOD;
divi = divi * G[u].size() % MOD;
}
for (auto p : downop[u]) {
ll h = lev + p.first;
if (h < n) {
levval[h] = (levval[h] - p.second * mul) % MOD;
if (levval[h] < 0) levval[h] += MOD;
}
}
}
int main()
{
// freopen("G.in", "r", stdin);
cin.tie(0)->sync_with_stdio(0);
// inv
inv[1] = 1;
for (ll i = 2; i < maxn; ++i) {
inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
}
cin >> n;
for (ll i = 1; i <= n; ++i) {
cin >> a[i];
}
ll u, v;
for (ll i = 1; i < n; ++i) {
cin >> u >> v;
G[u].push_back(v);
G[v].push_back(u);
}
ll q;
cin >> q;
for (ll i = 1; i <= q; ++i) {
cin >> type[i];
if (type[i] == '+') {
cin >> ind[i] >> val[i];
}
}
ll high = 0, cur = 0;
for (ll i = q; i > 0; --i) {
if (type[i] == '^') cur--;
else if (type[i] == 'v') cur++;
high = max(high, cur);
if (type[i] == '+') {
up[ind[i]].push_back(oper{high - cur, high, val[i]});
}
}
for (ll i = 1; i <= n; ++i) {
up[i].push_back(oper{high - cur, high, a[i]});
}
dfsup(1, -1, 0);
dfsdown(1, 0);
for (ll i = 1; i <= n; ++i) {
cout << ans[i] << ' ';
}
return 0;
}