算法
(树上差分) $O(N + Q)$
对于操作1而言,若 $a$ 的深度大于 $b$,就给以点 $a$ 为根的子树上每个点的点权 +x
,利用树上差分,只需要在点 $a$ 上打上 +x
的标记;否则就给不在以点 $b$ 为根的子树上的点的点权 +x
,这里可以做一点小转化,也就是可以将树上每个点的点权 +x
,同时将在以点 $a$ 为根的子树上的点的点权 -x
,那么我们就可以在根节点上打上 +x
的标记,并在点 $b$ 上打上 -x
的标记
对于操作2同理
然后我们可以利用 dfs
将每个点的标记下放从而更新每个点的权值。
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define fi first
#define se second
using std::cin;
using std::cout;
using std::vector;
using P = std::pair<int, int>;
using ll = long long;
vector<vector<int>> to;
vector<int> dep;
vector<ll> d;
// 求每个点的深度
void tfs(int v, int p = -1) {
for (int u : to[v]) {
if (u == p) continue;
dep[u] = dep[v] + 1;
tfs(u, v);
}
}
// v点标记下放
void dfs(int v, int p = -1) {
for (int u : to[v]) {
if (u == p) continue;
d[u] += d[v];
dfs(u, v);
}
}
int main() {
int n;
cin >> n;
to.resize(n);
dep.resize(n);
vector<P> es;
rep(i, n - 1) {
int a, b;
cin >> a >> b;
--a; --b;
to[a].push_back(b);
to[b].push_back(a);
es.emplace_back(a, b);
}
int q;
cin >> q;
tfs(0);
ll tot = 0;
d.resize(n);
rep(qi, q) {
int t, e, x;
cin >> t >> e >> x;
--t; --e;
int a = es[e].fi, b = es[e].se;
if (dep[a] > dep[b]) {
std::swap(a, b);
t ^= 1;
}
if (!t) {
tot += x;
x = -x;
}
d[b] += x;
}
dfs(0);
rep(i, n) {
d[i] += tot;
cout << d[i] << '\n';
}
return 0;
}