Hướng giải của Cập Nhật Đường Đi Trên Cây
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ả:
Hướng dẫn giải
Bài toán yêu cầu thực hiện truy vấn và cập nhật trên đường đi đơn giữa 2 đỉnh của cây. Sử dụng phương pháp Heavy-Light Decomposition (HLD) kết hợp Segment Tree:
- HLD phân rã cây thành các chuỗi xích đỉnh (heavy chain), các đỉnh thuộc mỗi chuỗi xích sẽ có chỉ số liên tục trên mảng Segment Tree.
- Khi cập nhật/truy vấn từ \(U\) đến \(V\), ta nhảy dần theo các chuỗi xích từ dưới lên trên (nhờ so sánh độ sâu của đỉnh đầu chuỗi head) cho đến khi cả hai đỉnh quy về cùng một chuỗi xích.
- Ở mỗi lần nhảy chuỗi xích, ta thực hiện cập nhật/truy vấn đoạn tương ứng trên cây Segment Tree.
Độ phức tạp thời gian: \(O(Q \log^2 N)\).
Mã nguồn C++ mẫu
#include <bits/stdc++.h>
using namespace std;
struct LazySeg {
int n; vector<long long> tree, lazy;
LazySeg(int size) { n = size; tree.assign(4*size, 0); lazy.assign(4*size, 0); }
void push(int node, int start, int end) {
if (lazy[node] == 0) return;
tree[node] += lazy[node] * (end - start + 1);
if (start != end) {
lazy[2*node] += lazy[node];
lazy[2*node+1] += lazy[node];
}
lazy[node] = 0;
}
void update(int node, int start, int end, int l, int r, long long val) {
push(node, start, end);
if (r < start || end < l) return;
if (l <= start && end <= r) { lazy[node] += val; push(node, start, end); return; }
int mid = (start + end)/2;
update(2*node, start, mid, l, r, val);
update(2*node+1, mid+1, end, l, r, val);
tree[node] = tree[2*node] + tree[2*node+1];
}
long long query(int node, int start, int end, int l, int r) {
push(node, start, end);
if (r < start || end < l) return 0;
if (l <= start && end <= r) return tree[node];
int mid = (start + end)/2;
return query(2*node, start, mid, l, r) + query(2*node+1, mid+1, end, l, r);
}
};
int n, q;
vector<vector<int>> adj;
vector<int> parent_node, depth, heavy, head, pos;
int cur_pos;
int dfs(int v, int p) {
parent_node[v] = p;
int size = 1;
int max_c_size = 0;
for (int c : adj[v]) {
if (c != p) {
depth[c] = depth[v] + 1;
int c_size = dfs(c, v);
size += c_size;
if (c_size > max_c_size) {
max_c_size = c_size;
heavy[v] = c;
}
}
}
return size;
}
void decompose(int v, int h) {
head[v] = h;
pos[v] = cur_pos++;
if (heavy[v] != -1) decompose(heavy[v], h);
for (int c : adj[v]) {
if (c != parent_node[v] && c != heavy[v]) {
decompose(c, c);
}
}
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(NULL);
if (!(cin >> n >> q)) return 0;
vector<int> a(n);
for (int i=0; i<n; i++) cin >> a[i];
adj.resize(n);
for (int i=0; i<n-1; i++) {
int u, v; cin >> u >> v; u--; v--;
adj[u].push_back(v); adj[v].push_back(u);
}
parent_node.assign(n, -1); depth.assign(n, 0); heavy.assign(n, -1);
head.assign(n, 0); pos.assign(n, 0);
cur_pos = 0;
dfs(0, -1);
decompose(0, 0);
LazySeg st(n);
for (int i=0; i<n; i++) st.update(1, 0, n-1, pos[i], pos[i], a[i]);
while (q--) {
int t, u, v; cin >> t >> u >> v; u--; v--;
if (t == 1) {
long long val; cin >> val;
while (head[u] != head[v]) {
if (depth[head[u]] > depth[head[v]]) swap(u, v);
st.update(1, 0, n-1, pos[head[v]], pos[v], val);
v = parent_node[head[v]];
}
if (depth[u] > depth[v]) swap(u, v);
st.update(1, 0, n-1, pos[u], pos[v], val);
} else {
long long total = 0;
while (head[u] != head[v]) {
if (depth[head[u]] > depth[head[v]]) swap(u, v);
total += st.query(1, 0, n-1, pos[head[v]], pos[v]);
v = parent_node[head[v]];
}
if (depth[u] > depth[v]) swap(u, v);
total += st.query(1, 0, n-1, pos[u], pos[v]);
cout << total << "\n";
}
}
}
Nhận xét