Charged Tree

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

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

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

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

AC代码

#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;
}