Editorial for Tàu điện không đổi chuyến
Submitting an official solution before solving the problem yourself is a bannable offence.
Gợi ý 1 - Khi nào một chuyến tàu đi được từ s đến t?
Vì đường đi giữa hai ga trong cây là duy nhất, Vũ đi được mà không đổi tàu khi và chỉ khi có một tuyến chứa toàn bộ đường đi từ s đến t. Hãy xem đây là bài toán kiểm tra một đường đi có nằm trọn trong đường đi của tuyến tàu hay không.
Gợi ý 2 - Gắn mỗi ga với một đoạn Euler
Root cây tại ga 1. Mỗi cây con khi đó là một đoạn liên tiếp [tin[u], tout[u]] trong thứ tự Euler. Ta lưu mỗi tuyến có hai đầu mút (a,b) thành cả hai điểm có hướng (tin[a],tin[b]) và (tin[b],tin[a]).
- Nếu
svàtnằm ở hai nhánh khác nhau, hai đầu mút tuyến phải lần lượt thuộc cây con củasvà cây con củat. - Nếu
slà tổ tiên củat, gọiclà người con củasnằm trên đường đếnt. Một đầu mút phải thuộc cây con củat; đầu còn lại phải nằm ngoài cây con củac.
Mỗi điều kiện trở thành một hoặc hai hình chữ nhật trên mặt phẳng Euler. Đếm điểm tuyến nằm trong các hình chữ nhật đó.
Lời giải đầy đủ
Biến truy vấn thành hình chữ nhật
Root cây tại ga 1, tính tin, tout, độ sâu và bảng tổ tiên nhị phân. Ta cần LCA để biết quan hệ tổ tiên giữa hai đầu truy vấn.
Hai ga không là tổ tiên của nhau. Đường đi giữa chúng rời cây con của s rồi đi vào cây con của t. Do đó, một đầu tuyến phải nằm trong cây con s, đầu kia nằm trong cây con t. Ta truy vấn hình chữ nhật:
[tin[s],tout[s]] × [tin[t],tout[t]].
Một ga là tổ tiên của ga còn lại. Đổi chỗ để s là tổ tiên của t. Gọi c là người con của s trên đường đến t. Một đầu tuyến phải ở cây con t; đầu còn lại phải ở ngoài cây con c, nếu không đường đi của tuyến không thể đi qua s. Phần bù của cây con c gồm hai đoạn Euler:
[1,tin[c]-1][tout[c]+1,N]
Vì vậy, trường hợp này cần kiểm tra hai hình chữ nhật có hoành độ thuộc cây con t và tung độ thuộc từng đoạn trên.
Đếm điểm trong các hình chữ nhật
Với mỗi hình chữ nhật [x_1,x_2] × [y_1,y_2], số điểm bên trong bằng hiệu của hai truy vấn tiền tố:
count(x <= x_2, y_1 <= y <= y_2) - count(x < x_1, y_1 <= y <= y_2).
Ta sắp xếp các điểm tuyến theo hoành độ. Mỗi truy vấn tiền tố trở thành một sự kiện tại x_2 hoặc x_1-1. Quét các sự kiện theo x; Fenwick tree lưu số điểm đã thêm theo tung độ. Một truy vấn trả lời YES nếu tổng số điểm tìm được lớn hơn 0.
Độ phức tạp
- Thời gian:
O((N+M+Q) log N). - Bộ nhớ:
O(N log N + M + Q).
Code C++17
#include <bits/stdc++.h>
using namespace std;
struct Fenwick {
int n;
vector<int> bit;
Fenwick(int n = 0) : n(n), bit(n + 1, 0) {}
void add(int i, int value) {
for (; i <= n; i += i & -i) bit[i] += value;
}
int prefixSum(int i) const {
int result = 0;
for (; i > 0; i -= i & -i) result += bit[i];
return result;
}
int rangeSum(int left, int right) const {
if (left > right) return 0;
return prefixSum(right) - prefixSum(left - 1);
}
};
struct Event {
int x, leftY, rightY, queryId, sign;
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m, q;
cin >> n >> m >> q;
vector<vector<int>> graph(n + 1);
for (int i = 1; i < n; ++i) {
int u, v;
cin >> u >> v;
graph[u].push_back(v);
graph[v].push_back(u);
}
const int LOG = 20;
vector<vector<int>> up(LOG, vector<int>(n + 1));
vector<int> parent(n + 1), depth(n + 1), tin(n + 1), tout(n + 1);
vector<int> nextEdge(n + 1, 0);
int timer = 0;
// DFS lap, tranh tran ngan xep khi cay la mot duong thang.
vector<int> stack = {1};
parent[1] = 1;
for (int j = 0; j < LOG; ++j) up[j][1] = 1;
tin[1] = ++timer;
while (!stack.empty()) {
int u = stack.back();
if (nextEdge[u] == (int)graph[u].size()) {
tout[u] = timer;
stack.pop_back();
continue;
}
int v = graph[u][nextEdge[u]++];
if (v == parent[u]) continue;
parent[v] = u;
depth[v] = depth[u] + 1;
up[0][v] = u;
for (int j = 1; j < LOG; ++j)
up[j][v] = up[j - 1][up[j - 1][v]];
tin[v] = ++timer;
stack.push_back(v);
}
auto isAncestor = [&](int u, int v) {
return tin[u] <= tin[v] && tout[v] <= tout[u];
};
auto lca = [&](int u, int v) {
if (isAncestor(u, v)) return u;
if (isAncestor(v, u)) return v;
for (int j = LOG - 1; j >= 0; --j) {
if (!isAncestor(up[j][u], v)) u = up[j][u];
}
return parent[u];
};
auto jump = [&](int u, int distance) {
for (int j = 0; j < LOG; ++j)
if (distance & (1 << j)) u = up[j][u];
return u;
};
vector<pair<int, int>> points;
points.reserve(2 * m);
for (int i = 0; i < m; ++i) {
int a, b;
cin >> a >> b;
points.push_back({tin[a], tin[b]});
points.push_back({tin[b], tin[a]});
}
sort(points.begin(), points.end());
vector<Event> events;
events.reserve(4 * q);
auto addRectangle = [&](int id, int x1, int x2, int y1, int y2) {
if (x1 > x2 || y1 > y2) return;
events.push_back({x2, y1, y2, id, +1});
events.push_back({x1 - 1, y1, y2, id, -1});
};
for (int id = 0; id < q; ++id) {
int s, t;
cin >> s >> t;
int w = lca(s, t);
if (w != s && w != t) {
addRectangle(id, tin[s], tout[s], tin[t], tout[t]);
} else {
if (w == t) swap(s, t);
int child = jump(t, depth[t] - depth[s] - 1);
addRectangle(id, tin[t], tout[t], 1, tin[child] - 1);
addRectangle(id, tin[t], tout[t], tout[child] + 1, n);
}
}
sort(events.begin(), events.end(), [](const Event& a, const Event& b) {
return a.x < b.x;
});
Fenwick fenwick(n);
vector<int> answerCount(q, 0);
int pointIndex = 0;
for (const Event& event : events) {
while (pointIndex < (int)points.size() && points[pointIndex].first <= event.x) {
fenwick.add(points[pointIndex].second, 1);
++pointIndex;
}
answerCount[event.queryId] += event.sign *
fenwick.rangeSum(event.leftY, event.rightY);
}
for (int count : answerCount)
cout << (count > 0 ? "YES" : "NO") << '\n';
return 0;
}