Hướng giải của Giao lộ giao thông
Nhớ rằng hướng dẫn giải này chỉ nên sử dụng khi bế tắc, và tuyệt đối không nên sao chép mã nguồn kèm theo. Hãy tôn trọng tác giả bài tập và người viết hướng dẫn giải.
Nộp mã nguồn lời giải chính thức trước khi giải bài tập đó có thể khiến bạn bị ban.
Nộp mã nguồn lời giải chính thức trước khi giải bài tập đó có thể khiến bạn bị ban.
Tác giả:
Bài toán này là ứng dụng của kĩ thuật Sai phân trên cây (Tree Difference) kết hợp Euler Tour phẳng hóa cây.
Với thao tác cộng \(x\) trên đường đi từ \(u\) đến \(v\):
diff[u] += x; diff[v] += x; diff[LCA] -= x; diff[parent[LCA]] -= x;
Khi đó, giá trị tích lũy của một đỉnh chính là tổng các giá trị diff trong cây con của nó.
Để cập nhật và truy vấn động điểm trên cây con, ta dùng Euler Tour để lưu lại tin[u] và tout[u]. Subtree của u tương ứng đoạn [tin[u], tout[u]]. Sử dụng cây Fenwick (BIT) để cập nhật và tính tổng trên đoạn.
Mã nguồn C++ mẫu
#include <bits/stdc++.h>
using namespace std;
const int LOG = 20;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, q;
if (!(cin >> n >> q)) return 0;
vector<vector<int>> adj(n + 1);
for (int i = 0; i < n - 1; i++) {
int u, v;
if (cin >> u >> v) {
adj[u].push_back(v);
adj[v].push_back(u);
}
}
vector<int> depth(n + 1, 0);
vector<vector<int>> up(n + 1, vector<int>(LOG, 0));
vector<int> tin(n + 1), tout(n + 1);
int timer = 0;
auto dfs = [&](auto self, int u, int p) -> void {
depth[u] = depth[p] + 1;
up[u][0] = p;
tin[u] = ++timer;
for (int k = 1; k < LOG; k++) {
up[u][k] = up[up[u][k-1]][k-1];
}
for (int v : adj[u]) {
if (v != p) {
self(self, v, u);
}
}
tout[u] = timer;
};
depth[0] = -1;
dfs(dfs, 1, 0);
auto lca = [&](int u, int v) -> int {
if (depth[u] < depth[v]) swap(u, v);
int diff = depth[u] - depth[v];
for (int k = 0; k < LOG; k++) {
if (diff & (1 << k)) {
u = up[u][k];
}
}
if (u == v) return u;
for (int k = LOG - 1; k >= 0; k--) {
if (up[u][k] != up[v][k]) {
u = up[u][k];
v = up[v][k];
}
}
return up[u][0];
};
vector<long long> bit(timer + 1, 0);
auto add = [&](int idx, long long val) {
if (idx <= 0) return;
for (; idx <= timer; idx += idx & -idx) {
bit[idx] += val;
}
};
auto query = [&](int idx) -> long long {
long long sum = 0;
for (; idx > 0; idx -= idx & -idx) {
sum += bit[idx];
}
return sum;
};
for (int i = 0; i < q; i++) {
int type;
if (cin >> type) {
if (type == 1) {
int u, v;
long long x;
if (cin >> u >> v >> x) {
int ancestor = lca(u, v);
add(tin[u], x);
add(tin[v], x);
add(tin[ancestor], -x);
add(tin[up[ancestor][0]], -x);
}
} else {
int u;
if (cin >> u) {
cout << query(tout[u]) - query(tin[u] - 1) << "\n";
}
}
}
}
return 0;
}
Nhận xét