Hướng giải của Sửa cạnh
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
Sử dụng thuật toán phù hợp để giải quyết bài toán.
Lời giải
Dùng kỹ thuật RMQ (Range Minimum Query) với Sparse Table hoặc Segment Tree.
Bài toán yêu cầu vừa cập nhật trọng số cạnh vừa truy vấn giá trị nhỏ nhất / lớn nhất trên đường đi. Sử dụng Heavy-Light Decomposition (HLD) kết hợp Segment Tree.
Tư tưởng:
- Gán mỗi cạnh cho đỉnh con (đỉnh sâu hơn).
- Dùng HLD để chia cây thành các chuỗi, mỗi chuỗi là một đoạn trên segment tree.
- Segment tree lưu giá trị nhỏ nhất và lớn nhất, hỗ trợ cập nhật điểm (khi sửa trọng số cạnh, cập nhật tại vị trí của đỉnh con).
- Truy vấn \((u,v)\): dùng HLD chia đường đi thành \(O(\log N)\) đoạn trên segment tree, mỗi đoạn truy vấn \(O(\log N)\), tổng \(O(\log^2 N)\).
Độ phức tạp: \(O(N)\) tiền xử lý, \(O(\log^2 N)\) mỗi truy vấn / cập nhật.
// Giải thuật rmqt cho bài toán rmqt-up-edge\n#include <bits/stdc++.h>
using namespace std;
struct SegTree {
int n;
vector<long long> mn, mx;
SegTree(int n): n(n), mn(4*n+5), mx(4*n+5) {}
void update(int id, int l, int r, int pos, long long val) {
if (l == r) { mn[id] = mx[id] = val; return; }
int m = (l+r)/2;
if (pos <= m) update(id*2, l, m, pos, val);
else update(id*2+1, m+1, r, pos, val);
mn[id] = min(mn[id*2], mn[id*2+1]);
mx[id] = max(mx[id*2], mx[id*2+1]);
}
pair<long long,long long> query(int id, int l, int r, int ql, int qr) {
if (ql > r || qr < l) return {LLONG_MAX, LLONG_MIN};
if (ql <= l && r <= qr) return {mn[id], mx[id]};
int m = (l+r)/2;
auto L = query(id*2, l, m, ql, qr);
auto R = query(id*2+1, m+1, r, ql, qr);
return {min(L.first, R.first), max(L.second, R.second)};
}
};
int main() {
// Doc du lieu dau vao
ios_base::sync_with_stdio(false); cin.tie(NULL);
int n; cin >> n;
vector<vector<pair<int,int>>> adj(n+1);
for (int i = 1; i < n; i++) {
int u,v,w; cin >> u >> v >> w;
adj[u].push_back({v,w}); adj[v].push_back({u,w});
}
vector<int> parent(n+1), depth(n+1), sz(n+1), heavy(n+1, -1);
vector<long long> val_at_node(n+1);
// DFS tinh kich thuoc cay con
function<int(int,int)> dfs = [&](int u, int p) {
parent[u] = p; depth[u] = depth[p] + 1; sz[u] = 1;
int max_sz = 0;
for (auto [v,w] : adj[u]) if (v != p) {
val_at_node[v] = w;
int sub = dfs(v, u);
sz[u] += sub;
if (sub > max_sz) { max_sz = sub; heavy[u] = v; }
}
return sz[u];
};
dfs(1, 0);
vector<int> head(n+1), pos(n+1);
int cur = 0;
function<void(int,int)> dec = [&](int u, int h) {
head[u] = h; pos[u] = ++cur;
if (heavy[u] != -1) dec(heavy[u], h);
for (auto [v,w] : adj[u])
if (v != parent[u] && v != heavy[u]) dec(v, v);
};
dec(1, 1);
SegTree seg(n);
for (int i = 2; i <= n; i++)
seg.update(1, 1, n, pos[i], val_at_node[i]);
auto path_query = [&](int u, int v) -> pair<long long,long long> {
long long mn = LLONG_MAX, mx = LLONG_MIN;
while (head[u] != head[v]) {
if (depth[head[u]] < depth[head[v]]) swap(u, v);
auto res = seg.query(1, 1, n, pos[head[u]], pos[u]);
mn = min(mn, res.first); mx = max(mx, res.second);
u = parent[head[u]];
}
if (depth[u] > depth[v]) swap(u, v);
if (u != v) {
auto res = seg.query(1, 1, n, pos[u]+1, pos[v]);
mn = min(mn, res.first); mx = max(mx, res.second);
}
return {mn, mx};
};
int q; cin >> q;
while (q--) {
int t; cin >> t;
if (t == 1) {
int u,v; long long w; cin >> u >> v >> w;
int child = (parent[u] == v) ? u : v;
seg.update(1, 1, n, pos[child], w);
} else {
int u,v; cin >> u >> v;
auto [mn,mx] = path_query(u, v);
cout << mn << " " << mx << "\n";
}
}
return 0;
}
Nhận xét