考虑将贡献表示出来:\(\forall v\in \text{subtree}_u\),\(v\) 会加上 \(x - (dep_v - dep_u)k\),然后发现这个东西可以维护整棵子树,即把 \(x,dep_u\times k\) 和 \(dep_v\times k\) 分开计算,然后 \(dep_v\) 可以最后再管,就变为子树加,单点和了。用树状数组维护 dfs 序即可。
代码:
#include<bits/stdc++.h>
using namespace std;
#define TIME 1e3 * clock() / CLOCKS_PER_SEC
#define L(i, j, k) for(int i = (j); i <= (k); ++i)
#define R(i, j, k) for(int i = (j); i >= (k); --i)
#define ll long long
#define eb emplace_back
const int mod = 1e9 + 7;
int n, m;
int dn, dfn[300010], sz[300010], dep[300010];
vector<int> e[300010];
struct BIT {
int v[300010];
void add(int x, int y) {
for(; x <= n; x += x & -x) v[x] = (v[x] + y) % mod;
}
int ask(int x) {
int res = 0;
for(; x; x -= x & -x) res = (res + v[x]) % mod;
return res;
}
void upd(int l, int r, int v) { add(l, v), add(r + 1, -v); };
} t1, t2;
void dfs(int x) {
dfn[x] = ++dn, sz[x] = 1;
for(int y : e[x]) dep[y] = dep[x] + 1, dfs(y), sz[x] += sz[y];
}
int main(){
ios :: sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n;
L(i, 2, n) {
int x; cin >> x;
e[x].eb(i);
}
dfs(1);
cin >> m;
L(_, 1, m) {
int opt, v; cin >> opt >> v;
if(opt == 1) {
int x, k; cin >> x >> k;
int l = dfn[v], r = dfn[v] + sz[v] - 1;
t1.upd(l, r, k), t2.upd(l, r, (dep[v] * 1ll * k + x) % mod);
} else {
cout << (t2.ask(dfn[v]) - t1.ask(dfn[v]) * 1ll * dep[v] % mod + 2 * mod) % mod << "\n";
}
}
cerr << TIME << "ms\n";
return 0;
}
接下来的部分没有代码。
这个方法可以扩展到全局操作。
对深度操作在根的时候是很方便的,考虑转化到根,这里可以采用对边赋值然后求树上前缀和的方法,但这里不需要对其兄弟产生贡献,所以没有必要转换到根。
具体地,令 \(u\) 为当前节点,给 \(u\) 子树内的边都减去 \(k\),然后给 \((u,fa_u)\) 这条边的权值加上 \(x\) 即可。所以这里需要树链剖分,且需支持区间加,区间和。