Hướng giải của Khoảng cách đỉnh xa
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ả:
Lời giải
Ý tưởng
Bài toán yêu cầu đếm số đỉnh cách \(u\) không quá \(K\). Sử dụng Centroid Decomposition:
Với mỗi centroid \(C\), lưu một vector chứa khoảng cách từ \(C\) đến tất cả các đỉnh trong subtree của nó, sắp xếp tăng dần.
Khi truy vấn \((u, K)\):
- Duyệt từ \(u\) lên centroid tree.
- Tại mỗi ancestor \(c\), tính \(d = dist(u, c)\). Nếu \(d \le K\): đếm số đỉnh trong vector của \(c\) có khoảng cách \(\le K - d\) (dùng binary search).
- Trừ đi phần đếm trùng từ subtree chứa \(u\) (lưu thêm vector riêng cho từng con).
Độ phức tạp
- Tiền xử lý: \(O(N \log N)\).
- Mỗi truy vấn: \(O(\log^2 N)\).
Code mẫu
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005, LOG = 17;
vector<int> adj[MAXN];
int subsize[MAXN], depth[MAXN], up[MAXN][LOG];
int centroid_parent[MAXN];
bool removed[MAXN];
vector<int> dists_up[MAXN], dists_down[MAXN];
int n;
void dfs_lca(int u, int p) {
up[u][0] = p;
for (int i = 1; i < LOG; i++)
up[u][i] = (up[u][i-1] == -1 ? -1 : up[up[u][i-1]][i-1]);
for (int v : adj[u])
if (v != p) { depth[v] = depth[u] + 1; dfs_lca(v, u); }
}
int lca(int u, int v) {
if (depth[u] < depth[v]) swap(u, v);
for (int i = LOG-1; i >= 0; i--)
if (up[u][i] != -1 && depth[up[u][i]] >= depth[v]) u = up[u][i];
if (u == v) return u;
for (int i = LOG-1; i >= 0; i--)
if (up[u][i] != up[v][i]) u = up[u][i], v = up[v][i];
return up[u][0];
}
int dist(int u, int v) { return depth[u] + depth[v] - 2*depth[lca(u,v)]; }
void dfs_size(int u, int p) {
subsize[u] = 1;
for (int v : adj[u])
if (v != p && !removed[v]) { dfs_size(v,u); subsize[u] += subsize[v]; }
}
int find_centroid(int u, int p, int tot) {
for (int v : adj[u])
if (v != p && !removed[v] && subsize[v] > tot/2) return find_centroid(v,u,tot);
return u;
}
void collect(int u, int p, int cent, vector<int>& out) {
out.push_back(dist(u, cent));
for (int v : adj[u])
if (v != p && !removed[v]) collect(v, u, cent, out);
}
void decompose(int u, int pc) {
dfs_size(u, -1);
int c = find_centroid(u, -1, subsize[u]);
centroid_parent[c] = pc;
removed[c] = true;
// Lưu khoảng cách từ c đến mọi đỉnh trong subtree
vector<int> all;
all.push_back(0);
for (int v : adj[c]) {
if (removed[v]) continue;
vector<int> tmp;
collect(v, c, c, tmp);
for (int d : tmp) all.push_back(d);
// Lưu riêng cho từng con (để trừ sau)
sort(tmp.begin(), tmp.end());
dists_down[v] = tmp;
}
sort(all.begin(), all.end());
dists_up[c] = all;
for (int v : adj[c])
if (!removed[v]) decompose(v, c);
}
int query(int u, int k) {
int res = 0, cur = u;
while (cur != -1) {
int d = dist(u, cur);
if (d <= k) {
// Đếm trong dists_up[cur] có bao nhiêu <= k - d
auto& vec = dists_up[cur];
int cnt = upper_bound(vec.begin(), vec.end(), k - d) - vec.begin();
res += cnt;
// Trừ phần đã đếm từ subtree chứa u
if (centroid_parent[cur] != -1) {
int p = centroid_parent[cur];
// Tìm con nào của p dẫn đến cur
int child = cur;
// Trừ dists_down của con đó
auto& down = dists_down[child];
int sub = upper_bound(down.begin(), down.end(), k - d) - down.begin();
res -= sub;
}
}
cur = centroid_parent[cur];
}
return res;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n;
for (int i = 0; i < n-1; i++) { int u,v; cin>>u>>v; adj[u].push_back(v); adj[v].push_back(u); }
memset(up, -1, sizeof(up));
dfs_lca(1, -1);
decompose(1, -1);
int q; cin >> q;
while (q--) {
int u, k; cin >> u >> k;
cout << query(u, k) << "\n";
}
return 0;
}
Nhận xét