CF396C On Changing Tree 题解

CF396C

考虑将贡献表示出来：\(\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\) 即可。所以这里需要树链剖分，且需支持区间加，区间和。