Hướng dẫn cho CAPITAL (Chọn ĐT'23-24)
Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.
Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.
Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.
Tóm tắt đề bài
Cho một cây gồm \(n\) đỉnh với gốc tại đỉnh \(1\). Mỗi đỉnh \(i\) có trọng số \(w_i\). Định nghĩa \(x\) quản lý \(y\) nếu \(x\) nằm trên đường đi từ \(y\) đến gốc \(1\) (tức \(x\) là tổ tiên của \(y\)). Cần thực hiện \(Q\) truy vấn thuộc hai loại:
- Loại 1: Tăng \(w_u\) thêm \(c\).
- Loại 2: Tăng \(w_v\) thêm \(c\) cho tất cả các đỉnh \(v\) thuộc cây con gốc \(u\).
Sau mỗi truy vấn, tìm đỉnh \(u\) sao cho tổng chi phí \(f(u) = \sum_{v=1}^n w_v \cdot d(u, v)\) là nhỏ nhất. Nếu có nhiều đỉnh thỏa mãn, chọn đỉnh có chỉ số nhỏ nhất.
Phân tích
Trọng tâm của cây có trọng số (Weighted Centroid)
Bài toán yêu cầu tìm đỉnh \(u\) tối thiểu hóa \(\sum w_v \cdot d(u, v)\). Đây là bài toán tìm trọng tâm (centroid) của cây khi các đỉnh có trọng số.
Một đỉnh \(u\) là trọng tâm nếu và chỉ nếu với mọi đỉnh \(v\) kề với \(u\), tổng trọng số của các đỉnh thuộc nhánh chứa \(v\) (khi bỏ cạnh \((u, v)\)) không vượt quá một nửa tổng trọng số của cả cây.
Gọi \(W\) là tổng trọng số tất cả các đỉnh: \(W = \sum_{i=1}^n w_i\).
Điều kiện để \(u\) là trọng tâm:
- Với mọi con \(v\) của \(u\): \(W_{sub}(v) \le \frac{W}{2}\)
- Với phía trên của \(u\) (cha của \(u\)): \(W - W_{sub}(u) \le \frac{W}{2}\)
Trong đó \(W_{sub}(u)\) là tổng trọng số của các đỉnh trong cây con gốc \(u\).
Tính chất
- Trọng tâm của cây luôn tồn tại. Có thể có 1 hoặc 2 trọng tâm (nếu có 2, chúng phải kề nhau).
- Nếu ta di chuyển từ một đỉnh \(u\) sang một đỉnh con \(v\), hàm chi phí \(f(u)\) sẽ thay đổi dựa trên sự chênh lệch trọng số giữa hai phía. Cụ thể, nếu \(W_{sub}(v) > \frac{W}{2}\), việc di chuyển từ \(u\) sang \(v\) chắc chắn làm giảm tổng chi phí.
Hướng giải quyết
1. Cấu trúc dữ liệu quản lý trọng số
Để thực hiện các truy vấn cập nhật:
- Loại 1: Cập nhật điểm trên cây con (thực chất là cập nhật tại \(tin[u]\) trong mảng DFS).
- Loại 2: Cập nhật đoạn trên cây con (\(tin[u]\) đến \(tout[u]\)).
Ta sử dụng Segment Tree với kỹ thuật Lazy Propagation để quản lý các giá trị \(w_i\) và tính tổng \(W_{sub}(u)\) một cách nhanh chóng. \(W_{sub}(u)\) chính là tổng các \(w_i\) trong đoạn \([tin[u], tout[u]]\).
2. Tìm trọng tâm bằng Centroid Decomposition
Thay vì duyệt tuần tự từ gốc (có thể mất \(O(n)\) trong trường hợp cây suy biến), ta sử dụng cấu trúc Cây trọng tâm (Centroid Tree) để tìm kiếm nhanh hơn.
- Xây dựng cây trọng tâm từ cây ban đầu. Với mỗi đỉnh \(u\) trong cây trọng tâm, ta lưu trữ:
up_centroid[u]: Centroid cấp trên.down_centroids[u]: Danh sách các centroid con.childs[u]: Đỉnh con tương ứng trong cây gốc dẫn đến nhánh chứa centroid con đó.
3. Thuật toán tìm kiếm
Bắt đầu từ một đỉnh bất kỳ (thường là centroid tổng của cả cây):
- Kiểm tra xem có nhánh con nào của \(u\) có tổng trọng số \(W_{sub} > \frac{W}{2}\) không.
- Nếu có một nhánh con \(v\) thỏa mãn \(W_{sub}(v) \cdot 2 > W\), ta di chuyển xuống centroid con nằm trong nhánh đó.
- Nếu có nhánh thỏa mãn \(W_{sub}(v) \cdot 2 = W\), thì cả \(u\) và \(v\) đều có thể là trọng tâm, ta lấy \(\min(u, p[u])\).
- Nếu không có nhánh nào thỏa mãn, \(u\) chính là trọng tâm.
Vì độ sâu của cây trọng tâm là \(O(\log n)\), mỗi lần tìm kiếm mất \(O(\log^2 n)\) hoặc \(O(\log n)\) tùy cách cài đặt.
Độ phức tạp
- Xây dựng: \(O(n \log n)\) để phân tách trọng tâm và xây dựng Segment Tree.
- Cập nhật: \(O(\log n)\) cho mỗi truy vấn loại 1 hoặc loại 2.
- Tìm kiếm: \(O(\log^2 n)\) do duyệt trên cây trọng tâm và truy vấn Segment Tree.
- Tổng quát: \(O(Q \log^2 n)\), thỏa mãn giới hạn thời gian.
Code tham khảo
C++
#include <bits/stdc++.h>
using namespace std;
typedef long long lli;
const int maxn = 1e5 + 5;
int n, Q, w[maxn], p[maxn];
vector<int> gr[maxn];
int tin[maxn], tout[maxn], arr[maxn], ntime = 0;
int sub[maxn];
bool del[maxn];
int up_centroid[maxn], tvert;
vector<int> down_centroids[maxn], childs[maxn];
struct segment_tree {
lli total[maxn * 4], lazy[maxn * 4];
int from[maxn * 4], to[maxn * 4];
void build(int x, int l, int r) {
from[x] = l; to[x] = r;
if(l == r) {
total[x] = w[arr[l]];
return;
}
int mid = (l + r) / 2;
build(x * 2, l, mid);
build(x * 2 + 1, mid + 1, r);
total[x] = total[x * 2] + total[x * 2 + 1];
}
void push(int x) {
if(lazy[x] == 0) return;
for(int i = x * 2; i <= x * 2 + 1; ++i) {
lazy[i] += lazy[x];
total[i] += (to[i] - from[i] + 1) * lazy[x];
}
lazy[x] = 0;
}
void update(int x, int l, int r, int L, int R, int k) {
if(L > r || l > R) return;
if(l >= L && r <= R) {
total[x] += (to[x] - from[x] + 1) * 1LL * k;
lazy[x] += k;
return;
}
push(x);
int mid = (l + r) / 2;
update(x * 2, l, mid, L, R, k);
update(x * 2 + 1, mid + 1, r, L, R, k);
total[x] = total[x * 2] + total[x * 2 + 1];
}
lli get(int x, int l, int r, int L, int R) {
if(L > r || l > R) return 0;
if(l >= L && r <= R) return total[x];
push(x);
int mid = (l + r) / 2;
return get(x * 2, l, mid, L, R) + get(x * 2 + 1, mid + 1, r, L, R);
}
} tree_data;
void dfs_prep(int u, int par) {
p[u] = par;
tin[u] = ++ntime;
arr[ntime] = u;
for(auto &v : gr[u]) if(v != par) dfs_prep(v, u);
tout[u] = ntime;
}
void dfs_calc_sub(int u, int par) {
sub[u] = 1;
for(auto &v : gr[u]) if(v != par && !del[v]) {
dfs_calc_sub(v, u);
sub[u] += sub[v];
}
}
int find_centroid(int u, int par, int all) {
for(auto &v : gr[u]) if(v != par && !del[v] && sub[v] * 2 > all)
return find_centroid(v, u, all);
return u;
}
int centroid_decompose(int u) {
dfs_calc_sub(u, 0);
u = find_centroid(u, 0, sub[u]);
del[u] = true;
for(auto &v : gr[u]) {
if(del[v]) continue;
if(v == p[u]) up_centroid[u] = centroid_decompose(v);
else {
down_centroids[u].push_back(centroid_decompose(v));
childs[u].push_back(v);
}
}
return u;
}
int get_ans(int u) {
lli total_w = tree_data.get(1, 1, n, 1, n);
lli sub_u = tree_data.get(1, 1, n, tin[u], tout[u]);
if(sub_u * 2 == total_w) return min(u, p[u]);
if(sub_u * 2 > total_w) {
for(int i = 0; i < childs[u].size(); ++i) {
if(tree_data.get(1, 1, n, tin[childs[u][i]], tout[childs[u][i]]) * 2 >= total_w)
return get_ans(down_centroids[u][i]);
}
return u;
}
return get_ans(up_centroid[u]);
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(0);
cin >> n >> Q;
for(int i = 1; i <= n; ++i) cin >> w[i];
for(int i = 1; i < n; ++i) {
int u, v; cin >> u >> v;
gr[u].push_back(v); gr[v].push_back(u);
}
dfs_prep(1, 0);
tvert = centroid_decompose(1);
tree_data.build(1, 1, n);
while(Q--) {
int t, u, c; cin >> t >> u >> c;
if(t == 1) tree_data.update(1, 1, n, tin[u], tin[u], c);
else tree_data.update(1, 1, n, tin[u], tout[u], c);
cout << get_ans(tvert) << "\n";
}
return 0;
}
Bình luận