Editorial for Lối về phía chân trời
Submitting an official solution before solving the problem yourself is a bannable offence.
Hướng 1 — Gợi ý 1: tìm ngưỡng chứa đáp án
Nén các giá trị của đỉnh thành thứ hạng tăng dần. Với một truy vấn, giá trị lớn thứ k cũng là giá trị nhỏ thứ (L-k+1), trong đó L là số đỉnh trên đường đi. Hãy tìm thứ hạng nhỏ nhất x sao cho đường đi có ít nhất L-k+1 đỉnh mang giá trị không vượt quá x.
Gợi ý 2: xử lý đồng thời nhiều phép tìm kiếm nhị phân
Trong một lượt, gom các truy vấn có cùng giá trị giữa. Quét thứ hạng từ nhỏ đến lớn và kích hoạt các đỉnh có thứ hạng không vượt quá ngưỡng hiện tại.
Khi kích hoạt một đỉnh, cộng 1 cho mọi đỉnh trong cây con của nó. Dùng Euler tour và Fenwick dạng cộng đoạn, hỏi điểm để biết có bao nhiêu đỉnh đang kích hoạt trên đường từ gốc đến một đỉnh. Từ đó dùng công thức đường đi qua LCA.
Lời giải và code — nhị phân song song
Đếm số đỉnh trên đường đi
Root cây tại đỉnh 1. Gọi rootCount[x] là số đỉnh đã kích hoạt trên đường từ gốc đến x. Với w = LCA(u,v), số đỉnh kích hoạt trên đường u-v là:
rootCount[u] + rootCount[v] - 2 * rootCount[w] + active[w].
Khi kích hoạt đỉnh x, rootCount tăng thêm 1 với mọi đỉnh trong cây con của x. Euler tour biến cây con thành một đoạn liên tiếp, vì vậy Fenwick hỗ trợ cộng đoạn và hỏi điểm.
Tìm thứ hạng
Đặt need = L-k+1. Nhị phân song song tìm thứ hạng nhỏ nhất sao cho số đỉnh trên đường đi có thứ hạng không vượt quá ngưỡng đạt ít nhất need. Trong mỗi lượt, các truy vấn được gom theo mid; khi quét mid tăng dần, ta chỉ cần kích hoạt thêm các đỉnh mới.
Độ phức tạp
Mỗi lượt dùng O(N+Q) thao tác nhóm và O(log N) cho mỗi kích hoạt hoặc truy vấn đường đi. Có O(log N) lượt, tổng thời gian O((N+Q) log^2 N), bộ nhớ O(N log N).
Code C++17
#include <bits/stdc++.h>
using namespace std;
struct Fenwick {
int n;
vector<int> bit;
Fenwick(int n) : n(n), bit(n + 2, 0) {}
void add(int index, int value) {
// index được đánh số từ 0; index = n dùng làm điểm kết thúc giả.
for (int i = index + 1; i <= n + 1; i += i & -i)
bit[i] += value;
}
void addRange(int left, int right, int value) {
add(left, value);
add(right + 1, -value);
}
int pointQuery(int index) const {
int result = 0;
for (int i = index + 1; i > 0; i -= i & -i)
result += bit[i];
return result;
}
};
struct Query {
int u, v, w, need;
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, q;
cin >> n >> q;
vector<int> value(n + 1), sortedValues;
for (int u = 1; u <= n; ++u) {
cin >> value[u];
sortedValues.push_back(value[u]);
}
vector<vector<int>> graph(n + 1);
for (int i = 0; i < n - 1; ++i) {
int u, v;
cin >> u >> v;
graph[u].push_back(v);
graph[v].push_back(u);
}
// DFS lặp để tránh tràn ngăn xếp khi cây là một đường thẳng.
vector<int> parent(n + 1), depth(n + 1), tin(n + 1), tout(n + 1), order;
order.reserve(n);
vector<int> stack = {1};
while (!stack.empty()) {
int u = stack.back();
stack.pop_back();
tin[u] = (int)order.size();
order.push_back(u);
for (int v : graph[u]) {
if (v == parent[u]) continue;
parent[v] = u;
depth[v] = depth[u] + 1;
stack.push_back(v);
}
}
vector<int> subtreeSize(n + 1, 1);
for (int i = n - 1; i > 0; --i)
subtreeSize[parent[order[i]]] += subtreeSize[order[i]];
for (int u = 1; u <= n; ++u)
tout[u] = tin[u] + subtreeSize[u] - 1;
int LOG = 1;
while ((1 << LOG) <= n) ++LOG;
vector<vector<int>> up(LOG, vector<int>(n + 1));
for (int u = 1; u <= n; ++u)
up[0][u] = (parent[u] == 0 ? u : parent[u]);
for (int j = 1; j < LOG; ++j)
for (int u = 1; u <= n; ++u)
up[j][u] = up[j - 1][up[j - 1][u]];
auto lca = [&](int u, int v) {
if (depth[u] < depth[v]) swap(u, v);
int difference = depth[u] - depth[v];
for (int j = 0; j < LOG; ++j)
if (difference & (1 << j)) u = up[j][u];
if (u == v) return u;
for (int j = LOG - 1; j >= 0; --j) {
if (up[j][u] != up[j][v]) {
u = up[j][u];
v = up[j][v];
}
}
return up[0][u];
};
sort(sortedValues.begin(), sortedValues.end());
sortedValues.erase(unique(sortedValues.begin(), sortedValues.end()), sortedValues.end());
int kinds = (int)sortedValues.size();
vector<int> rankValue(n + 1);
for (int u = 1; u <= n; ++u)
rankValue[u] = lower_bound(sortedValues.begin(), sortedValues.end(), value[u]) - sortedValues.begin();
vector<Query> queries(q);
for (int i = 0; i < q; ++i) {
int u, v, k;
cin >> u >> v >> k;
int w = lca(u, v);
int length = depth[u] + depth[v] - 2 * depth[w] + 1;
queries[i] = {u, v, w, length - k + 1};
}
vector<int> nodesByValue(n);
iota(nodesByValue.begin(), nodesByValue.end(), 1);
sort(nodesByValue.begin(), nodesByValue.end(), [&](int x, int y) {
return rankValue[x] < rankValue[y];
});
vector<int> low(q, 0), high(q, kinds - 1);
while (true) {
vector<int> head(kinds, -1), next(q, -1);
bool hasQuery = false;
for (int i = 0; i < q; ++i) {
if (low[i] == high[i]) continue;
hasQuery = true;
int mid = (low[i] + high[i]) / 2;
next[i] = head[mid];
head[mid] = i;
}
if (!hasQuery) break;
Fenwick fenwick(n);
int pointer = 0;
for (int mid = 0; mid < kinds; ++mid) {
while (pointer < n && rankValue[nodesByValue[pointer]] <= mid) {
int x = nodesByValue[pointer++];
fenwick.addRange(tin[x], tout[x], 1);
}
for (int id = head[mid]; id != -1; id = next[id]) {
const Query& qu = queries[id];
int count = fenwick.pointQuery(tin[qu.u])
+ fenwick.pointQuery(tin[qu.v])
- 2 * fenwick.pointQuery(tin[qu.w])
+ (rankValue[qu.w] <= mid);
if (count >= qu.need) high[id] = mid;
else low[id] = mid + 1;
}
}
}
for (int i = 0; i < q; ++i)
cout << sortedValues[low[i]] << '\n';
return 0;
}
Hướng 2 — Gợi ý 1: lưu các giá trị trên đường từ gốc
Root cây tại 1. Với mỗi đỉnh x, hãy lưu một cấu trúc đếm các giá trị trên đường từ gốc đến x. Truy vấn u-v có thể ghép từ bốn phiên bản gắn với u, v, LCA(u,v) và cha của LCA.
Gợi ý 2: cây đoạn persistent giữ tần suất
Nén các giá trị. Mỗi phiên bản là cây đoạn đếm số lần từng thứ hạng xuất hiện. Khi đi từ cha sang con, chỉ thêm giá trị của đỉnh con để tạo phiên bản mới.
Để tìm giá trị lớn thứ k, nhìn số lượng ở nửa phải trước. Nếu nửa phải có ít nhất k phần tử, đi tiếp vào đó; nếu không, trừ số lượng đó khỏi k rồi đi sang nửa trái.
Lời giải và code — cây đoạn persistent
Ghép đường đi
Gọi root[x] là phiên bản đếm các giá trị trên đường từ gốc đến x, có tính cả x. Với w = LCA(u,v), tần suất trên đường u-v bằng:
root[u] + root[v] - root[w] - root[parent(w)].
Công thức này giữ đúng số lần xuất hiện, kể cả khi nhiều đỉnh có cùng giá trị. Ở gốc, parent(w) được xem là đỉnh 0 với phiên bản rỗng.
Tìm phần tử lớn thứ k
Trong mỗi nút cây đoạn, cộng bốn tần suất theo dấu trong công thức trên. Xét nửa phải trước vì nửa này chứa các giá trị lớn hơn. Nếu nửa phải có ít hơn k phần tử, chuyển sang nửa trái với k mới bằng k trừ số phần tử nửa phải.
Độ phức tạp
Tạo N phiên bản mất O(N log N). Mỗi truy vấn cần LCA và đi xuống cây đoạn, thời gian O(log N). Bộ nhớ O(N log N).
Code C++17
#include <bits/stdc++.h>
using namespace std;
struct Node {
int left = 0, right = 0, sum = 0;
};
vector<Node> seg;
int update(int oldNode, int left, int right, int position) {
int current = (int)seg.size();
seg.push_back(seg[oldNode]);
++seg[current].sum;
if (left < right) {
int mid = (left + right) / 2;
if (position <= mid) {
int child = update(seg[current].left, left, mid, position);
seg[current].left = child;
} else {
int child = update(seg[current].right, mid + 1, right, position);
seg[current].right = child;
}
}
return current;
}
int kthLargest(int ru, int rv, int rw, int rparent,
int left, int right, int k) {
if (left == right) return left;
int mid = (left + right) / 2;
int countRight = seg[seg[ru].right].sum
+ seg[seg[rv].right].sum
- seg[seg[rw].right].sum
- seg[seg[rparent].right].sum;
if (k <= countRight) {
return kthLargest(seg[ru].right, seg[rv].right,
seg[rw].right, seg[rparent].right,
mid + 1, right, k);
}
return kthLargest(seg[ru].left, seg[rv].left,
seg[rw].left, seg[rparent].left,
left, mid, k - countRight);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, q;
cin >> n >> q;
vector<int> value(n + 1), sortedValues;
for (int u = 1; u <= n; ++u) {
cin >> value[u];
sortedValues.push_back(value[u]);
}
vector<vector<int>> graph(n + 1);
for (int i = 0; i < n - 1; ++i) {
int u, v;
cin >> u >> v;
graph[u].push_back(v);
graph[v].push_back(u);
}
vector<int> parent(n + 1), depth(n + 1), order;
order.reserve(n);
parent[1] = 0;
vector<int> stack = {1};
while (!stack.empty()) {
int u = stack.back();
stack.pop_back();
order.push_back(u);
for (int v : graph[u]) {
if (v == parent[u]) continue;
parent[v] = u;
depth[v] = depth[u] + 1;
stack.push_back(v);
}
}
int LOG = 1;
while ((1 << LOG) <= n) ++LOG;
vector<vector<int>> up(LOG, vector<int>(n + 1));
for (int u = 1; u <= n; ++u)
up[0][u] = parent[u] == 0 ? u : parent[u];
for (int j = 1; j < LOG; ++j)
for (int u = 1; u <= n; ++u)
up[j][u] = up[j - 1][up[j - 1][u]];
auto lca = [&](int u, int v) {
if (depth[u] < depth[v]) swap(u, v);
int difference = depth[u] - depth[v];
for (int j = 0; j < LOG; ++j)
if (difference & (1 << j)) u = up[j][u];
if (u == v) return u;
for (int j = LOG - 1; j >= 0; --j) {
if (up[j][u] != up[j][v]) {
u = up[j][u];
v = up[j][v];
}
}
return up[0][u];
};
sort(sortedValues.begin(), sortedValues.end());
sortedValues.erase(unique(sortedValues.begin(), sortedValues.end()), sortedValues.end());
int kinds = (int)sortedValues.size();
vector<int> rankValue(n + 1);
for (int u = 1; u <= n; ++u)
rankValue[u] = lower_bound(sortedValues.begin(), sortedValues.end(), value[u]) - sortedValues.begin();
seg.reserve((size_t)n * 20 + 1);
seg.push_back({0, 0, 0}); // phiên bản rỗng, cũng dùng cho đỉnh 0
vector<int> root(n + 1, 0);
for (int u : order) {
int previous = (u == 1 ? 0 : root[parent[u]]);
root[u] = update(previous, 0, kinds - 1, rankValue[u]);
}
while (q--) {
int u, v, k;
cin >> u >> v >> k;
int w = lca(u, v);
int position = kthLargest(root[u], root[v], root[w], root[parent[w]],
0, kinds - 1, k);
cout << sortedValues[position] << '\n';
}
return 0;
}