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