Bài 34: LCA và nhảy nhị phân trong C++ và Python: tổ tiên chung gần nhất, tổ tiên thứ k, khoảng cách trên cây
Lời mở đầu
Ở bài 33 em đã quen với cây: chọn gốc, tính cha, độ sâu, kích thước cây con bằng DFS, rồi quy hoạch động trên cây. Những bài đó chỉ cần một lần duyệt là xong. Đề thi HSG lại rất thích kiểu khác: cho một cây cố định và hàng trăm nghìn câu hỏi, mỗi câu hỏi về đường đi giữa hai đỉnh: hai đỉnh cách nhau bao xa, cạnh nặng nhất trên đường đi là bao nhiêu, đỉnh thứ $k$ trên đường đi là đỉnh nào… Chạy lại BFS/DFS (bài 21) cho từng câu hỏi thì quá chậm.
Chìa khoá của mọi câu hỏi đó là tổ tiên chung gần nhất (LCA, viết tắt của Lowest Common Ancestor): đường đi giữa $u$ và $v$ luôn đi lên tới LCA rồi đi xuống. Hôm nay ta học kỹ thuật nhảy nhị phân (binary lifting) để tìm LCA trong $O(\log n)$. Kỹ thuật này là sự kết hợp của hai thứ em đã biết: viết một số thành tổng các lũy thừa của 2 (thao tác bit, bài 20) và tư duy “thử bước lớn trước” của tìm kiếm nhị phân (bài 16).
up[k][u] (tổ tiên thứ $2^k$) và công thức xây bảng $2^k = 2^{k-1} + 2^{k-1}$; thuật toán LCA bằng nhảy nhị phân $O(\log n)$ mỗi truy vấn và vì sao nó đúng; các ứng dụng: khoảng cách hai đỉnh, tổ tiên thứ k, cạnh lớn nhất trên đường đi; thứ tự DFS tin/tout để kiểm tra tổ tiên trong $O(1)$, và ý tưởng LCA bằng Euler tour + RMQ. Có khung chạy tay LCA, 3 mô phỏng từng bước và 8 bài tập kèm gợi ý.Lộ trình bài viết, bấm vào từng phần để nhảy tới:
Phần 1Tổ tiên chung gần nhất là gì?
Cho một cây $n$ đỉnh, ta chọn đỉnh 1 làm gốc. Nhắc lại vài khái niệm từ bài 33:
- Cha của $v$ là đỉnh kề với $v$ nằm trên đường từ $v$ về gốc. Độ sâu
dep[v]là số cạnh từ gốc tới $v$ (gốc có độ sâu 0). - Tổ tiên của $v$ là mọi đỉnh nằm trên đường đi từ $v$ lên gốc, tính cả chính $v$. Ví dụ ở Hình 1, tổ tiên của 9 là 9, 5, 2, 1.
- Tổ tiên chung của $u$ và $v$ là đỉnh vừa là tổ tiên của $u$, vừa là tổ tiên của $v$. Gốc luôn là một tổ tiên chung.
- LCA(u, v) là tổ tiên chung sâu nhất, tức là gần $u$ và $v$ nhất.
Hình 1. Cây ví dụ dùng xuyên suốt bài (gốc 1). Đường đi từ 12 tới 9 đi lên 12 → 11 → 7 → 4 → 2 rồi xuống 2 → 5 → 9. Đỉnh cao nhất trên đường đi chính là LCA(12, 9) = 2.
| Cặp đỉnh | Tổ tiên của đỉnh thứ nhất | Tổ tiên của đỉnh thứ hai | LCA |
|---|---|---|---|
| 12, 9 | 12, 11, 7, 4, 2, 1 | 9, 5, 2, 1 | 2 |
| 12, 8 | 12, 11, 7, 4, 2, 1 | 8, 4, 2, 1 | 4 |
| 10, 12 | 10, 6, 3, 1 | 12, 11, 7, 4, 2, 1 | 1 |
| 7, 11 | 7, 4, 2, 1 | 11, 7, 4, 2, 1 | 7 (7 là tổ tiên của 11) |
Bảng 1. LCA là tổ tiên chung đầu tiên gặp được khi đi từ dưới lên. Nếu $u$ là tổ tiên của $v$ thì LCA chính là $u$.
Vì sao LCA quan trọng? Trên cây, giữa hai đỉnh chỉ có đúng một đường đi đơn, và đường đi đó luôn gồm hai đoạn: từ $u$ đi lên tới $l = $ LCA(u, v), rồi từ $l$ đi xuống tới $v$. Biết $l$ là biết hình dạng đường đi, ví dụ độ dài đường đi là $\text{dep}[u] + \text{dep}[v] - 2 \cdot \text{dep}[l]$. Với cặp (12, 9): $5 + 3 - 2 \cdot 1 = 6$ cạnh, đúng như Hình 1.
Cách ngây thơ. Trước hết duyệt BFS một lần từ gốc để có par[v] và dep[v]. Với mỗi truy vấn:
- Đỉnh nào sâu hơn thì cho leo lên cha từng bước, tới khi hai đỉnh cùng độ sâu.
- Cho cả hai cùng leo lên cha từng bước, tới khi chúng trùng nhau. Đỉnh gặp nhau chính là LCA.
Bước 2 đúng vì hai đỉnh cùng độ sâu thì tổ tiên chung của chúng cũng nằm ở cùng độ sâu với nhau: cứ leo song song, lần đầu tiên trùng nhau là tổ tiên chung sâu nhất.
| Bước | u (độ sâu) | v (độ sâu) | Việc làm |
|---|---|---|---|
| 1 | 12 (5) | 9 (3) | u sâu hơn → u lên cha |
| 2 | 11 (4) | 9 (3) | u vẫn sâu hơn → u lên cha |
| 3 | 7 (3) | 9 (3) | cùng độ sâu, 7 ≠ 9 → cả hai lên cha |
| 4 | 4 (2) | 5 (2) | 4 ≠ 5 → cả hai lên cha |
| 5 | 2 (1) | 2 (1) | trùng nhau → LCA = 2 |
Bảng 2. Tìm LCA(12, 9) bằng cách leo từng bước: mất 6 lần leo, đúng bằng độ dài đường đi.
Xem code C++ / Python: lca ngây thơ, leo từng bước (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200005;
int n, q, par[MAXN], dep[MAXN];
vector<int> adj[MAXN];
int lca(int u, int v){
while(dep[u] > dep[v]) u = par[u]; // đưa đỉnh sâu hơn lên cùng độ sâu
while(dep[v] > dep[u]) v = par[v];
while(u != v){ // cùng leo từng bước tới khi gặp nhau
u = par[u];
v = par[v];
}
return u;
}
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> q;
for(int i = 1; i < n; i++){
int u, v; cin >> u >> v;
adj[u].push_back(v); adj[v].push_back(u);
}
vector<int> order = {1}; // BFS từ gốc 1: tính cha và độ sâu
vector<bool> seen(n + 1, false);
seen[1] = true; par[1] = 0;
for(int i = 0; i < (int)order.size(); i++){
int u = order[i];
for(int v : adj[u]) if(!seen[v]){
seen[v] = true; par[v] = u; dep[v] = dep[u] + 1;
order.push_back(v);
}
}
while(q--){
int u, v; cin >> u >> v;
cout << lca(u, v) << "\n";
}
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n, q = int(data[0]), int(data[1])
adj = [[] for _ in range(n + 1)]
p = 2
for _ in range(n - 1):
u, v = int(data[p]), int(data[p + 1]); p += 2
adj[u].append(v); adj[v].append(u)
par = [0] * (n + 1); dep = [0] * (n + 1)
seen = [False] * (n + 1); seen[1] = True
order = [1] # BFS từ gốc 1: tính cha và độ sâu
for u in order:
for v in adj[u]:
if not seen[v]:
seen[v] = True; par[v] = u; dep[v] = dep[u] + 1
order.append(v)
out = []
for _ in range(q):
u, v = int(data[p]), int(data[p + 1]); p += 2
while dep[u] > dep[v]: u = par[u] # đưa đỉnh sâu hơn lên
while dep[v] > dep[u]: v = par[v]
while u != v: # cùng leo từng bước
u = par[u]; v = par[v]
out.append(u)
print('\n'.join(map(str, out)))
main()Phần 2Bảng nhảy nhị phân up[k][u]
Ý tưởng: thay vì chỉ biết cha (tổ tiên cách 1 bước), mỗi đỉnh nhớ thêm tổ tiên cách 2, 4, 8, 16, … bước. Gọi
up[k][u] = tổ tiên thứ $2^k$ của $u$ (đi lên từ $u$ đúng $2^k$ cạnh).Vì sao lại là lũy thừa của 2? Vì mọi số tự nhiên đều viết được thành tổng các lũy thừa của 2 khác nhau, chính là biểu diễn nhị phân (bài 20). Muốn đi lên 13 bước, ta viết $13 = 1101_2 = 8 + 4 + 1$ và nhảy 3 cú: 8 bước, 4 bước, 1 bước. Mỗi cú tra bảng $O(1)$, nên đi lên $d$ bước chỉ tốn $O(\log d)$ thay vì $O(d)$.
Xây bảng. Hàng $k = 0$ chính là cha: up[0][u] = par[u]. Với $k \ge 1$, nhảy $2^k$ bước bằng nhảy $2^{k-1}$ bước hai lần:
Đây đúng là một công thức quy hoạch động: hàng $k$ chỉ cần hàng $k - 1$ đã tính xong. Ta tính lần lượt từng hàng $k = 1, 2, \ldots$, mỗi hàng duyệt mọi đỉnh. Còn nhảy quá gốc thì sao? Ta quy ước cha của gốc là chính nó (up[0][1] = 1): nhảy quá gốc thì đứng yên ở gốc. Quy ước này làm thuật toán LCA ở phần 3 gọn hơn nhiều.
| u | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| dep[u] | 0 | 1 | 1 | 2 | 2 | 2 | 3 | 3 | 3 | 3 | 4 | 5 |
| up[0] (2^0 = 1 bước) | 1 | 1 | 1 | 2 | 2 | 3 | 4 | 4 | 5 | 6 | 7 | 11 |
| up[1] (2^1 = 2 bước) | 1 | 1 | 1 | 1 | 1 | 1 | 2 | 2 | 2 | 3 | 4 | 7 |
| up[2] (2^2 = 4 bước) | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 2 |
Bảng 3. Bảng nhảy nhị phân của cây ở Hình 1. Ví dụ up[2][12]: nhảy 2 bước 12 → 7 (up[1][12] = 7), rồi thêm 2 bước 7 → 2 (up[1][7] = 2), nên up[2][12] = 2. Ô xanh là chỗ đã nhảy chạm hoặc vượt quá gốc. Cây sâu nhất 5 nên 3 hàng ($2^0, 2^1, 2^2$) là đủ.
Đọc công thức thì thấy đơn giản, nhưng tự điền vài ô mới thấm. Em bấm Tiếp để xem từng ô được điền: đường vàng là cú nhảy $2^{k-1}$ đầu tiên, đường xanh lá là cú nhảy $2^{k-1}$ thứ hai. Có thể đổi cây tuỳ thích:
const int LOG = 18; // 2^LOG phải lớn hơn độ sâu lớn nhất (n ≤ 2e5 → 18)
int up[LOG][MAXN], dep[MAXN];
// sau khi BFS/DFS từ gốc: up[0][v] = cha của v, up[0][root] = root
for(int k = 1; k < LOG; k++)
for(int v = 1; v <= n; v++)
up[k][v] = up[k - 1][up[k - 1][v]];int, khoảng 14 MB.up[k][v] cần ô up[k-1][x] của một đỉnh $x$ khác. (Nếu muốn để vòng đỉnh ngoài thì phải duyệt đỉnh theo thứ tự BFS/DFS, cha trước con.)2. LOG quá nhỏ. Cần $2^{\text{LOG}} >$ độ sâu lớn nhất, nếu không cú nhảy lớn nhất không đủ xa. Với cây đường thẳng $n$ đỉnh, độ sâu là $n - 1$.
3. Khai báo
up[MAXN][LOG] cũng đúng, nhưng up[LOG][MAXN] chạy nhanh hơn vì khi xây bảng ta duyệt liên tiếp một hàng trong bộ nhớ.Phần 3LCA bằng nhảy nhị phân trong O(log n)
Giữ nguyên hai giai đoạn của cách ngây thơ, nhưng thay “leo từng bước” bằng “nhảy theo lũy thừa của 2”:
- Đưa về cùng độ sâu. Giả sử $u$ sâu hơn, đặt $d = \text{dep}[u] - \text{dep}[v]$. Với mỗi bit $k$ bằng 1 trong $d$, cho
u = up[k][u]. Sau đó $u$ và $v$ cùng độ sâu. Nếu lúc này $u = v$ thì $v$ là tổ tiên của đỉnh ban đầu, đáp án là $u$. - Cùng nhảy, càng xa càng tốt nhưng không được gặp nhau. Duyệt $k$ từ lớn xuống nhỏ: nếu
up[k][u] != up[k][v]thì cho cả hai nhảy:u = up[k][u],v = up[k][v]. Nếu hai đích trùng nhau thì không nhảy. Kết thúc vòng lặp, $u$ và $v$ đứng ngay dưới LCA, đáp án làup[0][u].
Vì sao giai đoạn 2 đúng? Gọi $D$ là số bước từ $u$ (và từ $v$, vì cùng độ sâu) lên tới LCA. Xét câu hỏi “sau $j$ bước, $u$ và $v$ đã gặp nhau chưa?”. Với $j < D$: chưa gặp (hai đỉnh khác nhau). Với $j \ge D$: đã gặp (cùng ở LCA hoặc cao hơn). Câu trả lời có dạng chưa, chưa, …, chưa, rồi, rồi, …, giống hệt điều kiện đơn điệu của tìm kiếm nhị phân. Ta đang tìm $j$ lớn nhất mà vẫn “chưa gặp”, tức $j = D - 1$, bằng cách dựng từng bit của nó từ cao xuống thấp: thử cộng thêm $2^k$, nếu vẫn chưa gặp thì giữ lại cú nhảy đó. Đây chính là chặt nhị phân trên các bit. Sau vòng lặp, $u, v$ đã đi đúng $D - 1$ bước, chỉ cần thêm 1 bước nữa là tới LCA.
Vì sao không được nhảy khi hai đích trùng nhau? Vì đỉnh trùng đó là một tổ tiên chung, nhưng có thể cao hơn LCA (đã vượt quá). Ta không biết đã vượt bao xa, nên an toàn nhất là không nhảy và thử cú nhỏ hơn.
| Giai đoạn | k | up[k][u] | up[k][v] | Quyết định | u, v sau bước |
|---|---|---|---|---|---|
| 1: đưa về cùng độ sâu | 1 | up[1][12] = 7 | – | $d = 5 - 3 = 2 = 10_2$: bit 1 bật → u nhảy 2 bước | u = 7, v = 9 |
| 2: cùng nhảy | 2 | up[2][7] = 1 | up[2][9] = 1 | trùng → không nhảy | u = 7, v = 9 |
| 2: cùng nhảy | 1 | up[1][7] = 2 | up[1][9] = 2 | trùng → không nhảy | u = 7, v = 9 |
| 2: cùng nhảy | 0 | up[0][7] = 4 | up[0][9] = 5 | khác → nhảy | u = 4, v = 5 |
| kết thúc | đáp án = up[0][4] | LCA = 2 |
Bảng 4. Tìm LCA(12, 9) bằng nhảy nhị phân với bảng 3. Chú ý ở k = 1: đỉnh 2 trùng nhau và đó đúng là LCA, nhưng thuật toán không biết điều đó, nên vẫn không nhảy. Nó dừng ngay dưới LCA rồi mới bước lên.
Em xem từng cú nhảy trên cây trong mô phỏng dưới đây. Thử thêm cặp $u, v$ mà một đỉnh là tổ tiên của đỉnh kia (ví dụ 7 và 12), và một cây dạng đường thẳng (nhập 1 2 3 4 5 6 7 8):
Xem code C++ / Python: lca bằng nhảy nhị phân (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200005, LOG = 18; // 2^18 > 200000
int n, q, up[LOG][MAXN], dep[MAXN];
vector<int> adj[MAXN];
int lca(int u, int v){
if(dep[u] < dep[v]) swap(u, v); // u là đỉnh sâu hơn
int d = dep[u] - dep[v];
for(int k = 0; k < LOG; k++) // giai đoạn 1: đưa u lên cùng độ sâu với v
if(d >> k & 1) u = up[k][u];
if(u == v) return u;
for(int k = LOG - 1; k >= 0; k--) // giai đoạn 2: nhảy xa nhất mà chưa gặp nhau
if(up[k][u] != up[k][v]){
u = up[k][u];
v = up[k][v];
}
return up[0][u]; // u, v đang đứng ngay dưới LCA
}
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> q;
for(int i = 1; i < n; i++){
int u, v; cin >> u >> v;
adj[u].push_back(v); adj[v].push_back(u);
}
vector<int> order = {1}; // BFS từ gốc 1: cha up[0][v] và độ sâu dep[v]
vector<bool> seen(n + 1, false);
seen[1] = true; up[0][1] = 1; // quy ước: cha của gốc là chính nó
for(int i = 0; i < (int)order.size(); i++){
int u = order[i];
for(int v : adj[u]) if(!seen[v]){
seen[v] = true; up[0][v] = u; dep[v] = dep[u] + 1;
order.push_back(v);
}
}
for(int k = 1; k < LOG; k++) // xây bảng: nhảy 2^k = nhảy 2^(k-1) hai lần
for(int v = 1; v <= n; v++)
up[k][v] = up[k - 1][up[k - 1][v]];
while(q--){
int u, v; cin >> u >> v;
cout << lca(u, v) << "\n";
}
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n, q = int(data[0]), int(data[1])
adj = [[] for _ in range(n + 1)]
p = 2
for _ in range(n - 1):
u, v = int(data[p]), int(data[p + 1]); p += 2
adj[u].append(v); adj[v].append(u)
LOG = max(1, n.bit_length()) # 2^LOG > n > độ sâu lớn nhất
par = [0] * (n + 1); dep = [0] * (n + 1)
par[1] = 1 # quy ước: cha của gốc là chính nó
seen = [False] * (n + 1); seen[1] = True
order = [1]
for u in order: # BFS từ gốc 1
for v in adj[u]:
if not seen[v]:
seen[v] = True; par[v] = u; dep[v] = dep[u] + 1
order.append(v)
up = [par]
for k in range(1, LOG): # nhảy 2^k = nhảy 2^(k-1) hai lần
prev = up[-1]
up.append([prev[prev[v]] for v in range(n + 1)])
rows_desc = up[::-1] # các hàng theo thứ tự k giảm dần
def lca(u, v):
if dep[u] < dep[v]:
u, v = v, u
d, k = dep[u] - dep[v], 0
while d: # giai đoạn 1: theo từng bit của d
if d & 1:
u = up[k][u]
d >>= 1; k += 1
if u == v:
return u
for row in rows_desc: # giai đoạn 2: k từ LOG - 1 về 0
a, b = row[u], row[v]
if a != b: # nhảy xa nhất mà chưa gặp nhau
u, v = a, b
return par[u]
out = []
for _ in range(q):
u, v = int(data[p]), int(data[p + 1]); p += 2
out.append(lca(u, v))
print('\n'.join(map(str, out)))
main()Khung chạy tay dưới đây chạy đúng chương trình trên với cây nhỏ (LOG = 4 đủ cho cây tối đa 15 đỉnh). Em quan sát cách BFS điền hàng up[0] và dep, cách mỗi hàng up[k] được suy ra từ hàng trên, rồi hai giai đoạn của hàm lca:
sys.stdin.buffer và dùng BFS thay cho DFS đệ quy (Python giới hạn độ sâu đệ quy khoảng 1000).if(u == v) return u; sau giai đoạn 1: thiếu nó, thuật toán trả về cha của LCA khi một đỉnh là tổ tiên của đỉnh kia.Phần 4Ứng dụng: khoảng cách, tổ tiên thứ k, cạnh lớn nhất
1. Khoảng cách giữa hai đỉnh. Với $l = $ LCA(u, v), đường đi gồm $\text{dep}[u] - \text{dep}[l]$ cạnh đi lên và $\text{dep}[v] - \text{dep}[l]$ cạnh đi xuống:
Nếu cạnh có trọng số, thay độ sâu bằng $D[v]$ = tổng trọng số từ gốc tới $v$ (tính luôn trong lúc BFS: $D[v] = D[\text{cha}] + w$), khi đó độ dài đường đi là $D[u] + D[v] - 2D[l]$. Phần đường từ gốc tới $l$ được tính hai lần trong $D[u] + D[v]$ nên phải trừ đi hai lần. Nhớ dùng long long cho $D$.
2. Tổ tiên thứ k. Đây chính là giai đoạn 1 của LCA: viết $k$ ở hệ nhị phân, bit $b$ nào bằng 1 thì nhảy u = up[b][u]. Nhớ kiểm tra $k \le \text{dep}[u]$ trước: nếu $k$ lớn hơn độ sâu thì không có tổ tiên đó (với quy ước cha của gốc là gốc, nhảy quá sẽ “dính” ở gốc và cho đáp án sai). Ví dụ tổ tiên thứ 5 của 12: $5 = 101_2$, nhảy 1 bước 12 → 11, rồi 4 bước 11 → 1.
Mô phỏng sau tách $k$ thành từng bit và nhảy từng cú. Em thử $k$ lớn hơn độ sâu của $u$ để thấy trường hợp “không tồn tại”:
3. Cạnh lớn nhất (hoặc nhỏ nhất) trên đường đi. Nhảy nhị phân không chỉ lưu “đi tới đâu” mà còn lưu được “đi qua những gì”. Thêm bảng thứ hai:
mx[k][u] = trọng số lớn nhất trong $2^k$ cạnh đi từ $u$ lên up[k][u].Hàng đầu mx[0][u] là trọng số cạnh nối $u$ với cha. Nhảy $2^k$ = hai lần nhảy $2^{k-1}$, nên cạnh lớn nhất là số lớn hơn trong hai đoạn: mx[k][u] = max(mx[k-1][u], mx[k-1][up[k-1][u]]). Khi tìm LCA, mỗi lần nhảy ta cập nhật best = max(best, mx[k][u]), và cuối giai đoạn 2 cộng thêm hai cạnh cuối cùng đi vào LCA. Cách làm y hệt cho cạnh nhỏ nhất, tổng (thay vì dùng $D$), hay bất cứ phép toán nào có tính kết hợp.
up: val[k][u] = ghep(val[k-1][u], val[k-1][up[k-1][u]]). Đây cũng là ý tưởng của Sparse Table mà em sẽ học ở bài 37.Chương trình dưới đây nhận cây có trọng số, mỗi truy vấn in ra độ dài đường đi và cạnh lớn nhất trên đường đi giữa $u$ và $v$. Ví dụ với cây 5 đỉnh: 1 – 2 (3), 1 – 3 (8), 2 – 4 (5), 2 – 5 (1). Đường 4 → 2 → 1 → 3 dài $5 + 3 + 8 = 16$, cạnh lớn nhất 8.
Xem code C++ / Python: khoảng cách và cạnh lớn nhất trên đường đi (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200005, LOG = 18;
int n, q, up[LOG][MAXN], mx[LOG][MAXN], dep[MAXN];
long long D[MAXN]; // tổng trọng số từ gốc tới v
vector<pair<int, int>> adj[MAXN]; // (đỉnh kề, trọng số)
// trả về (LCA, cạnh lớn nhất trên đường đi u - v)
pair<int, int> query(int u, int v){
int best = 0;
if(dep[u] < dep[v]) swap(u, v);
int d = dep[u] - dep[v];
for(int k = 0; k < LOG; k++)
if(d >> k & 1){ best = max(best, mx[k][u]); u = up[k][u]; }
if(u == v) return {u, best};
for(int k = LOG - 1; k >= 0; k--)
if(up[k][u] != up[k][v]){
best = max({best, mx[k][u], mx[k][v]});
u = up[k][u]; v = up[k][v];
}
best = max({best, mx[0][u], mx[0][v]}); // hai cạnh cuối đi vào LCA
return {up[0][u], best};
}
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> q;
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> order = {1};
vector<bool> seen(n + 1, false);
seen[1] = true; up[0][1] = 1; mx[0][1] = 0;
for(int i = 0; i < (int)order.size(); i++){
int u = order[i];
for(auto [v, w] : adj[u]) if(!seen[v]){
seen[v] = true; up[0][v] = u; mx[0][v] = w; // mx[0][v] = trọng số cạnh v - cha
dep[v] = dep[u] + 1; D[v] = D[u] + w;
order.push_back(v);
}
}
for(int k = 1; k < LOG; k++)
for(int v = 1; v <= n; v++){
int mid = up[k - 1][v];
up[k][v] = up[k - 1][mid];
mx[k][v] = max(mx[k - 1][v], mx[k - 1][mid]);
}
while(q--){
int u, v; cin >> u >> v;
auto [l, best] = query(u, v);
cout << D[u] + D[v] - 2 * D[l] << " " << best << "\n";
}
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n, q = int(data[0]), int(data[1])
adj = [[] for _ in range(n + 1)]
p = 2
for _ in range(n - 1):
u, v, w = int(data[p]), int(data[p + 1]), int(data[p + 2]); p += 3
adj[u].append((v, w)); adj[v].append((u, w))
LOG = max(1, n.bit_length())
par = [0] * (n + 1); m0 = [0] * (n + 1); dep = [0] * (n + 1); D = [0] * (n + 1)
par[1] = 1
seen = [False] * (n + 1); seen[1] = True
order = [1]
for u in order:
for v, w in adj[u]:
if not seen[v]:
seen[v] = True; par[v] = u; m0[v] = w # m0[v] = trọng số cạnh v - cha
dep[v] = dep[u] + 1; D[v] = D[u] + w
order.append(v)
up, mx = [par], [m0]
for k in range(1, LOG):
pu, pm = up[-1], mx[-1]
up.append([pu[pu[v]] for v in range(n + 1)])
mx.append([max(pm[v], pm[pu[v]]) for v in range(n + 1)])
def query(u, v): # (LCA, cạnh lớn nhất trên đường đi)
best = 0
if dep[u] < dep[v]:
u, v = v, u
d, k = dep[u] - dep[v], 0
while d:
if d & 1:
best = max(best, mx[k][u]); u = up[k][u]
d >>= 1; k += 1
if u == v:
return u, best
for k in range(LOG - 1, -1, -1):
if up[k][u] != up[k][v]:
best = max(best, mx[k][u], mx[k][v])
u = up[k][u]; v = up[k][v]
return up[0][u], max(best, mx[0][u], mx[0][v])
out = []
for _ in range(q):
u, v = int(data[p]), int(data[p + 1]); p += 2
l, best = query(u, v)
out.append('%d %d' % (D[u] + D[v] - 2 * D[l], best))
print('\n'.join(out))
main()Phần 5Thứ tự DFS tin/tout và LCA bằng Euler tour
Khi duyệt DFS từ gốc, ghi lại thời điểm vào tin[u] (đếm từ 1, tăng mỗi khi vào một đỉnh mới) và thời điểm ra tout[u] = giá trị bộ đếm lúc rời $u$, tức là tin lớn nhất trong cây con của $u$. Vì DFS đi hết cây con của $u$ rồi mới rời $u$, các đỉnh trong cây con của $u$ có tin nằm liền một đoạn $[\text{tin}[u], \text{tout}[u]]$. Từ đó:
Kiểm tra tổ tiên chỉ còn $O(1)$, không cần leo gì cả.
Hình 2. Đoạn $[\text{tin}, \text{tout}]$ của mỗi đỉnh (DFS thăm con theo thứ tự số tăng dần). Đoạn của 4 là [3, 7]; 12 có tin = 6 nằm trong đoạn nên 4 là tổ tiên của 12; 9 có tin = 9 nằm ngoài nên 4 không phải tổ tiên của 9.
LCA bằng tin/tout. Có hàm isAnc rồi, LCA viết gọn hơn nữa và không cần mảng độ sâu: nếu $u$ là tổ tiên của $v$ (hoặc ngược lại) thì trả lời ngay. Nếu không, đưa $u$ lên cao nhất có thể mà chưa là tổ tiên của $v$: duyệt $k$ từ lớn xuống nhỏ, nếu up[k][u] chưa phải tổ tiên của $v$ thì nhảy. Cuối cùng cha của $u$ là LCA. Đây vẫn là chặt nhị phân trên các bit, chỉ đổi điều kiện “chưa gặp nhau” thành “chưa là tổ tiên”.
Xem code C++ / Python: lca bằng tin/tout và nhảy nhị phân (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200005, LOG = 18;
int n, q, up[LOG][MAXN], tin[MAXN], tout[MAXN];
vector<int> adj[MAXN];
bool isAnc(int u, int v){ // u có phải tổ tiên của v (kể cả u = v)?
return tin[u] <= tin[v] && tin[v] <= tout[u];
}
int lca(int u, int v){
if(isAnc(u, v)) return u;
if(isAnc(v, u)) return v;
for(int k = LOG - 1; k >= 0; k--) // đưa u lên cao nhất mà CHƯA là tổ tiên của v
if(!isAnc(up[k][u], v)) u = up[k][u];
return up[0][u];
}
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> q;
for(int i = 1; i < n; i++){
int u, v; cin >> u >> v;
adj[u].push_back(v); adj[v].push_back(u);
}
// DFS không đệ quy (cây dạng đường thẳng sâu 2e5 dễ tràn ngăn xếp nếu đệ quy)
int timer = 0;
vector<int> st = {1}, it(n + 1, 0);
up[0][1] = 1; tin[1] = ++timer;
while(!st.empty()){
int u = st.back();
if(it[u] < (int)adj[u].size()){
int v = adj[u][it[u]++];
if(v == up[0][u]) continue; // bỏ qua cạnh về cha
up[0][v] = u; tin[v] = ++timer; // vào đỉnh v
st.push_back(v);
} else {
tout[u] = timer; // rời u: tout = tin lớn nhất trong cây con
st.pop_back();
}
}
for(int k = 1; k < LOG; k++)
for(int v = 1; v <= n; v++)
up[k][v] = up[k - 1][up[k - 1][v]];
while(q--){
int u, v; cin >> u >> v;
cout << lca(u, v) << "\n";
}
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n, q = int(data[0]), int(data[1])
adj = [[] for _ in range(n + 1)]
p = 2
for _ in range(n - 1):
u, v = int(data[p]), int(data[p + 1]); p += 2
adj[u].append(v); adj[v].append(u)
LOG = max(1, n.bit_length())
par = [0] * (n + 1); par[1] = 1
tin = [0] * (n + 1); tout = [0] * (n + 1)
timer = 1; tin[1] = 1
st, it = [1], [0] * (n + 1)
while st: # DFS không đệ quy
u = st[-1]
if it[u] < len(adj[u]):
v = adj[u][it[u]]; it[u] += 1
if v == par[u]:
continue
par[v] = u; timer += 1; tin[v] = timer
st.append(v)
else:
tout[u] = timer # tin lớn nhất trong cây con của u
st.pop()
up = [par]
for k in range(1, LOG):
prev = up[-1]
up.append([prev[prev[v]] for v in range(n + 1)])
def is_anc(u, v):
return tin[u] <= tin[v] <= tout[u]
def lca(u, v):
if is_anc(u, v):
return u
if is_anc(v, u):
return v
for k in range(LOG - 1, -1, -1):
w = up[k][u]
if not is_anc(w, v):
u = w
return up[0][u]
out = []
for _ in range(q):
u, v = int(data[p]), int(data[p + 1]); p += 2
out.append(lca(u, v))
print('\n'.join(map(str, out)))
main()it[u] nhớ đã xét tới đỉnh kề thứ mấy của $u$, hết đỉnh kề thì rời $u$ (ghi tout).LCA bằng Euler tour + RMQ. Có một cách nhìn hoàn toàn khác. Khi DFS, ghi đỉnh hiện tại vào một dãy mỗi khi vào đỉnh đó và mỗi khi quay về nó từ một con. Dãy này (gọi là Euler tour) có đúng $2n - 1$ phần tử. Gọi first[u] là vị trí xuất hiện đầu tiên của $u$. Trên đoạn từ first[u] tới first[v], DFS đi từ $u$ sang $v$ nên chắc chắn đi qua LCA, và không bao giờ lên cao hơn LCA. Vậy:
| vị trí | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| đỉnh | 1 | 2 | 4 | 7 | 11 | 12 | 11 | 7 | 4 | 8 | 4 | 2 | 5 | 9 | 5 | 2 | 1 | 3 | 6 | 10 | 6 | 3 | 1 |
| độ sâu | 0 | 1 | 2 | 3 | 4 | 5 | 4 | 3 | 2 | 3 | 2 | 1 | 2 | 3 | 2 | 1 | 0 | 1 | 2 | 3 | 2 | 1 | 0 |
Bảng 5. Euler tour của cây Hình 1 (23 phần tử). Đoạn từ first[12] = 5 tới first[9] = 13 (tô màu) có độ sâu nhỏ nhất bằng 1 tại đỉnh 2, đúng là LCA(12, 9).
Bài toán LCA biến thành bài tìm min trên đoạn (RMQ, Range Minimum Query) của một mảng cố định. Dùng Segment Tree (bài 31) thì mỗi truy vấn $O(\log n)$. Dùng Sparse Table thì sau khi chuẩn bị $O(n \log n)$, mỗi truy vấn chỉ $O(1)$. Em sẽ học Sparse Table kỹ ở bài 37, và sẽ thấy nó cũng dùng đúng ý tưởng “đoạn dài $2^k$ = hai đoạn dài $2^{k-1}$” của hôm nay.
| Cách làm | Chuẩn bị | Mỗi truy vấn | Bộ nhớ | Dùng khi |
|---|---|---|---|---|
| Leo từng bước | $O(n)$ | $O(\text{độ sâu})$, xấu nhất $O(n)$ | $O(n)$ | ít truy vấn, hoặc cây được đảm bảo thấp |
| Nhảy nhị phân | $O(n \log n)$ | $O(\log n)$ | $O(n \log n)$ | mặc định khi đi thi; làm được cả tổ tiên thứ k, max cạnh |
| Euler tour + Segment Tree | $O(n)$ | $O(\log n)$ | $O(n)$ | khi bộ nhớ chật |
| Euler tour + Sparse Table | $O(n \log n)$ | $O(1)$ | $O(n \log n)$ | số truy vấn rất lớn ($10^6$ trở lên) |
Bảng 6. So sánh các cách tìm LCA.
- Software (SOFTWARE) (Olympic 30/4 2023 – Tin học khối 10) (Trung bình)
- Bữa Tiệc (BUATIEC) (HSG12 Lâm Đồng 2025 – Bài 4) (Trung bình)
- Công Ty (HSG12 Hà Nội 2023 Vòng 1 – Bài 4) (Khó)
- Smallest Missing Genetic Value in Each Subtree (LeetCode 2003) (Khó)
Bài tậpLuyện LCA và nhảy nhị phân
Công ty có $n$ nhân viên ($1 \le n \le 2 \cdot 10^5$), nhân viên 1 là giám đốc. Với $i \ge 2$, sếp trực tiếp của nhân viên $i$ là $p_i$ (đảm bảo tạo thành một cây gốc 1). Có $q$ câu hỏi ($q \le 2 \cdot 10^5$), mỗi câu cho $u$ và $k$ ($0 \le k \le n$): đi lên $k$ cấp từ $u$ thì gặp ai? In $-1$ nếu không tồn tại.
Input: dòng đầu $n, q$; dòng hai $p_2, p_3, \ldots, p_n$; $q$ dòng sau mỗi dòng $u, k$.
12 4
1 1 2 2 3 4 4 5 6 7 11
12 5
12 3
9 4
10 01
4
-1
10📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
up[0][1] = 0, và đỉnh 0 có up[k][0] = 0, nghĩa là “đã rơi ra ngoài cây”. Nhờ vậy không cần mảng độ sâu: nhảy xong mà đứng ở 0 thì in $-1$. Thêm nữa, hàng up[k] chỉ cần hàng up[k-1] nên không cần BFS, cha cho theo thứ tự nào cũng được. Ví dụ: 12 lên 5 cấp: 11, 7, 4, 2, 1. Đỉnh 9 chỉ có 3 cấp phía trên nên lên 4 cấp là không tồn tại.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200005, LOG = 18;
int up[LOG][MAXN]; // up[k][v] = 0 nghĩa là "không tồn tại"
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int n, q;
cin >> n >> q;
up[0][1] = 0; // gốc không có cha
for(int i = 2; i <= n; i++) cin >> up[0][i];
for(int k = 1; k < LOG; k++)
for(int v = 1; v <= n; v++)
up[k][v] = up[k - 1][up[k - 1][v]]; // up[k][0] luôn bằng 0
while(q--){
int u, k;
cin >> u >> k;
for(int b = 0; b < LOG && u != 0; b++)
if(k >> b & 1) u = up[b][u];
cout << (u == 0 ? -1 : u) << "\n";
}
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n, q = int(data[0]), int(data[1])
par = [0, 0] + [int(x) for x in data[2:n + 1]] # par[1] = 0: gốc không có cha
LOG = max(1, n.bit_length())
up = [par]
for k in range(1, LOG):
prev = up[-1]
up.append([prev[prev[v]] for v in range(n + 1)]) # prev[0] = 0
p = n + 1
out = []
for _ in range(q):
u, k = int(data[p]), int(data[p + 1]); p += 2
b = 0
while k and u:
if k & 1:
u = up[b][u]
k >>= 1; b += 1
out.append(u if u else -1)
print('\n'.join(map(str, out)))
main()Cho cây $n$ đỉnh ($n, q \le 2 \cdot 10^5$) và $q$ truy vấn, mỗi truy vấn hỏi đường đi từ $u$ tới $v$ gồm bao nhiêu cạnh.
Input: dòng đầu $n, q$; $n - 1$ dòng tiếp mỗi dòng một cạnh $u, v$; $q$ dòng sau mỗi dòng $u, v$.
12 4
1 2
1 3
2 4
2 5
3 6
4 7
4 8
5 9
6 10
7 11
11 12
12 9
10 12
8 8
7 116
8
0
1📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200005, LOG = 18;
int n, q, up[LOG][MAXN], dep[MAXN];
vector<int> adj[MAXN];
int lca(int u, int v){
if(dep[u] < dep[v]) swap(u, v);
int d = dep[u] - dep[v];
for(int k = 0; k < LOG; k++)
if(d >> k & 1) u = up[k][u];
if(u == v) return u;
for(int k = LOG - 1; k >= 0; k--)
if(up[k][u] != up[k][v]){ u = up[k][u]; v = up[k][v]; }
return up[0][u];
}
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> q;
for(int i = 1; i < n; i++){
int u, v; cin >> u >> v;
adj[u].push_back(v); adj[v].push_back(u);
}
vector<int> order = {1};
vector<bool> seen(n + 1, false);
seen[1] = true; up[0][1] = 1;
for(int i = 0; i < (int)order.size(); i++){
int u = order[i];
for(int v : adj[u]) if(!seen[v]){
seen[v] = true; up[0][v] = u; dep[v] = dep[u] + 1;
order.push_back(v);
}
}
for(int k = 1; k < LOG; k++)
for(int v = 1; v <= n; v++)
up[k][v] = up[k - 1][up[k - 1][v]];
while(q--){
int u, v; cin >> u >> v;
cout << dep[u] + dep[v] - 2 * dep[lca(u, v)] << "\n";
}
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n, q = int(data[0]), int(data[1])
adj = [[] for _ in range(n + 1)]
p = 2
for _ in range(n - 1):
u, v = int(data[p]), int(data[p + 1]); p += 2
adj[u].append(v); adj[v].append(u)
LOG = max(1, n.bit_length())
par = [0] * (n + 1); dep = [0] * (n + 1); par[1] = 1
seen = [False] * (n + 1); seen[1] = True
order = [1]
for u in order:
for v in adj[u]:
if not seen[v]:
seen[v] = True; par[v] = u; dep[v] = dep[u] + 1
order.append(v)
up = [par]
for k in range(1, LOG):
prev = up[-1]
up.append([prev[prev[v]] for v in range(n + 1)])
def lca(u, v):
if dep[u] < dep[v]:
u, v = v, u
d, k = dep[u] - dep[v], 0
while d:
if d & 1:
u = up[k][u]
d >>= 1; k += 1
if u == v:
return u
for k in range(LOG - 1, -1, -1):
if up[k][u] != up[k][v]:
u = up[k][u]; v = up[k][v]
return up[0][u]
out = []
for _ in range(q):
u, v = int(data[p]), int(data[p + 1]); p += 2
out.append(dep[u] + dep[v] - 2 * dep[lca(u, v)])
print('\n'.join(map(str, out)))
main()Cho cây $n$ đỉnh gốc 1 ($n, q \le 2 \cdot 10^5$). Mỗi truy vấn cho $u, v$: hỏi $u$ có phải tổ tiên của $v$ không (một đỉnh được coi là tổ tiên của chính nó). In YES hoặc NO.
Input: dòng đầu $n, q$; $n - 1$ dòng tiếp là các cạnh; $q$ dòng sau mỗi dòng $u, v$.
12 5
1 2
1 3
2 4
2 5
3 6
4 7
4 8
5 9
6 10
7 11
11 12
1 12
4 12
12 4
3 9
5 5YES
YES
NO
NO
YES📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
tin, tout như phần 5, rồi kiểm tra $\text{tin}[u] \le \text{tin}[v] \le \text{tout}[u]$ trong $O(1)$. Ở Hình 2: đoạn của 4 là [3, 7], tin[12] = 6 nằm trong nên YES; đoạn của 12 là [6, 6], tin[4] = 3 nằm ngoài nên NO. Nhớ viết DFS không đệ quy.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200005;
int n, q, par[MAXN], tin[MAXN], tout[MAXN];
vector<int> adj[MAXN];
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> q;
for(int i = 1; i < n; i++){
int u, v; cin >> u >> v;
adj[u].push_back(v); adj[v].push_back(u);
}
int timer = 0;
vector<int> st = {1}, it(n + 1, 0);
par[1] = 0; tin[1] = ++timer;
while(!st.empty()){
int u = st.back();
if(it[u] < (int)adj[u].size()){
int v = adj[u][it[u]++];
if(v == par[u]) continue;
par[v] = u; tin[v] = ++timer;
st.push_back(v);
} else {
tout[u] = timer;
st.pop_back();
}
}
while(q--){
int u, v; cin >> u >> v;
bool ok = tin[u] <= tin[v] && tin[v] <= tout[u];
cout << (ok ? "YES" : "NO") << "\n";
}
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n, q = int(data[0]), int(data[1])
adj = [[] for _ in range(n + 1)]
p = 2
for _ in range(n - 1):
u, v = int(data[p]), int(data[p + 1]); p += 2
adj[u].append(v); adj[v].append(u)
par = [0] * (n + 1); tin = [0] * (n + 1); tout = [0] * (n + 1)
timer = 1; tin[1] = 1
st, it = [1], [0] * (n + 1)
while st:
u = st[-1]
if it[u] < len(adj[u]):
v = adj[u][it[u]]; it[u] += 1
if v == par[u]:
continue
par[v] = u; timer += 1; tin[v] = timer
st.append(v)
else:
tout[u] = timer
st.pop()
out = []
for _ in range(q):
u, v = int(data[p]), int(data[p + 1]); p += 2
out.append('YES' if tin[u] <= tin[v] <= tout[u] else 'NO')
print('\n'.join(out))
main()Có $n$ thành phố nối với nhau bởi $n - 1$ con đường tạo thành một cây ($n, q \le 2 \cdot 10^5$), con đường thứ $i$ dài $w_i$ ($1 \le w_i \le 10^9$). Mỗi truy vấn hỏi độ dài đường đi giữa hai thành phố $u$ và $v$.
Input: dòng đầu $n, q$; $n - 1$ dòng tiếp mỗi dòng $u, v, w$; $q$ dòng sau mỗi dòng $u, v$.
6 3
1 2 3
1 3 5
2 4 2
2 5 7
3 6 1
4 5
4 6
6 69
11
0📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
long long. Ví dụ (4, 6): LCA là 1, $D[4] = 5$, $D[6] = 6$, đáp án $5 + 6 = 11$.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200005, LOG = 18;
int n, q, up[LOG][MAXN], dep[MAXN];
long long D[MAXN]; // tổng trọng số từ gốc tới v
vector<pair<int, int>> adj[MAXN];
int lca(int u, int v){
if(dep[u] < dep[v]) swap(u, v);
int d = dep[u] - dep[v];
for(int k = 0; k < LOG; k++)
if(d >> k & 1) u = up[k][u];
if(u == v) return u;
for(int k = LOG - 1; k >= 0; k--)
if(up[k][u] != up[k][v]){ u = up[k][u]; v = up[k][v]; }
return up[0][u];
}
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> q;
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> order = {1};
vector<bool> seen(n + 1, false);
seen[1] = true; up[0][1] = 1;
for(int i = 0; i < (int)order.size(); i++){
int u = order[i];
for(auto [v, w] : adj[u]) if(!seen[v]){
seen[v] = true; up[0][v] = u; dep[v] = dep[u] + 1; D[v] = D[u] + w;
order.push_back(v);
}
}
for(int k = 1; k < LOG; k++)
for(int v = 1; v <= n; v++)
up[k][v] = up[k - 1][up[k - 1][v]];
while(q--){
int u, v; cin >> u >> v;
cout << D[u] + D[v] - 2 * D[lca(u, v)] << "\n";
}
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n, q = int(data[0]), int(data[1])
adj = [[] for _ in range(n + 1)]
p = 2
for _ in range(n - 1):
u, v, w = int(data[p]), int(data[p + 1]), int(data[p + 2]); p += 3
adj[u].append((v, w)); adj[v].append((u, w))
LOG = max(1, n.bit_length())
par = [0] * (n + 1); dep = [0] * (n + 1); D = [0] * (n + 1); par[1] = 1
seen = [False] * (n + 1); seen[1] = True
order = [1]
for u in order:
for v, w in adj[u]:
if not seen[v]:
seen[v] = True; par[v] = u; dep[v] = dep[u] + 1; D[v] = D[u] + w
order.append(v)
up = [par]
for k in range(1, LOG):
prev = up[-1]
up.append([prev[prev[v]] for v in range(n + 1)])
def lca(u, v):
if dep[u] < dep[v]:
u, v = v, u
d, k = dep[u] - dep[v], 0
while d:
if d & 1:
u = up[k][u]
d >>= 1; k += 1
if u == v:
return u
for k in range(LOG - 1, -1, -1):
if up[k][u] != up[k][v]:
u = up[k][u]; v = up[k][v]
return up[0][u]
out = []
for _ in range(q):
u, v = int(data[p]), int(data[p + 1]); p += 2
out.append(D[u] + D[v] - 2 * D[lca(u, v)])
print('\n'.join(map(str, out)))
main()Cho cây $n$ đỉnh ($n, q \le 2 \cdot 10^5$). Mỗi truy vấn cho $u, v, k$ ($0 \le k \le n$): liệt kê các đỉnh trên đường đi từ $u$ tới $v$ theo thứ tự, đánh số từ 0 (đỉnh số 0 là $u$). In ra đỉnh số $k$, hoặc $-1$ nếu đường đi có ít hơn $k + 1$ đỉnh.
Input: dòng đầu $n, q$; $n - 1$ dòng tiếp là các cạnh; $q$ dòng sau mỗi dòng $u, v, k$.
12 6
1 2
1 3
2 4
2 5
3 6
4 7
4 8
5 9
6 10
7 11
11 12
12 9 0
12 9 3
12 9 5
12 9 6
12 9 7
9 12 212
4
5
9
-1
2📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200005, LOG = 18;
int n, q, up[LOG][MAXN], dep[MAXN];
vector<int> adj[MAXN];
int lca(int u, int v){
if(dep[u] < dep[v]) swap(u, v);
int d = dep[u] - dep[v];
for(int k = 0; k < LOG; k++)
if(d >> k & 1) u = up[k][u];
if(u == v) return u;
for(int k = LOG - 1; k >= 0; k--)
if(up[k][u] != up[k][v]){ u = up[k][u]; v = up[k][v]; }
return up[0][u];
}
int kth(int u, int k){ // tổ tiên thứ k của u (k <= dep[u])
for(int b = 0; b < LOG; b++)
if(k >> b & 1) u = up[b][u];
return u;
}
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> q;
for(int i = 1; i < n; i++){
int u, v; cin >> u >> v;
adj[u].push_back(v); adj[v].push_back(u);
}
vector<int> order = {1};
vector<bool> seen(n + 1, false);
seen[1] = true; up[0][1] = 1;
for(int i = 0; i < (int)order.size(); i++){
int u = order[i];
for(int v : adj[u]) if(!seen[v]){
seen[v] = true; up[0][v] = u; dep[v] = dep[u] + 1;
order.push_back(v);
}
}
for(int k = 1; k < LOG; k++)
for(int v = 1; v <= n; v++)
up[k][v] = up[k - 1][up[k - 1][v]];
while(q--){
int u, v, k; cin >> u >> v >> k;
int l = lca(u, v);
int du = dep[u] - dep[l], dist = du + dep[v] - dep[l];
if(k > dist) cout << -1 << "\n";
else if(k <= du) cout << kth(u, k) << "\n"; // đỉnh nằm trên đoạn u -> l
else cout << kth(v, dist - k) << "\n"; // đỉnh nằm trên đoạn l -> v
}
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n, q = int(data[0]), int(data[1])
adj = [[] for _ in range(n + 1)]
p = 2
for _ in range(n - 1):
u, v = int(data[p]), int(data[p + 1]); p += 2
adj[u].append(v); adj[v].append(u)
LOG = max(1, n.bit_length())
par = [0] * (n + 1); dep = [0] * (n + 1); par[1] = 1
seen = [False] * (n + 1); seen[1] = True
order = [1]
for u in order:
for v in adj[u]:
if not seen[v]:
seen[v] = True; par[v] = u; dep[v] = dep[u] + 1
order.append(v)
up = [par]
for k in range(1, LOG):
prev = up[-1]
up.append([prev[prev[v]] for v in range(n + 1)])
def lca(u, v):
if dep[u] < dep[v]:
u, v = v, u
d, k = dep[u] - dep[v], 0
while d:
if d & 1:
u = up[k][u]
d >>= 1; k += 1
if u == v:
return u
for k in range(LOG - 1, -1, -1):
if up[k][u] != up[k][v]:
u = up[k][u]; v = up[k][v]
return up[0][u]
def kth(u, k): # tổ tiên thứ k của u (k <= dep[u])
b = 0
while k:
if k & 1:
u = up[b][u]
k >>= 1; b += 1
return u
out = []
for _ in range(q):
u, v, k = int(data[p]), int(data[p + 1]), int(data[p + 2]); p += 3
l = lca(u, v)
du = dep[u] - dep[l]
dist = du + dep[v] - dep[l]
if k > dist:
out.append(-1)
elif k <= du:
out.append(kth(u, k)) # trên đoạn u -> l
else:
out.append(kth(v, dist - k)) # trên đoạn l -> v
print('\n'.join(map(str, out)))
main()Mạng giao thông có $n$ thành phố và $m$ con đường hai chiều ($n \le 10^5$, $n - 1 \le m \le 2 \cdot 10^5$), đồ thị liên thông, con đường $i$ có độ nguy hiểm $w_i$ ($1 \le w_i \le 10^9$). Độ nguy hiểm của một lộ trình là độ nguy hiểm lớn nhất của các con đường trên lộ trình. Có $q$ câu hỏi ($q \le 2 \cdot 10^5$): đi từ $u$ tới $v$ thì độ nguy hiểm nhỏ nhất có thể là bao nhiêu? (In 0 nếu $u = v$.)
Input: dòng đầu $n, m, q$; $m$ dòng tiếp mỗi dòng $u, v, w$; $q$ dòng sau mỗi dòng $u, v$.
5 7 5
1 2 4
1 3 1
2 3 2
2 4 7
3 4 5
4 5 3
3 5 8
1 2
1 5
2 4
4 5
3 32
5
5
3
0📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
mx[k][u] như phần 4. Ví dụ: cây khung gồm 1–3 (1), 2–3 (2), 4–5 (3), 3–4 (5); đường từ 1 tới 5 là 1 – 3 – 4 – 5, cạnh lớn nhất là 5.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200005, LOG = 18;
int n, m, q, up[LOG][MAXN], mx[LOG][MAXN], dep[MAXN], dsu[MAXN];
vector<pair<int, int>> adj[MAXN];
int find(int x){ return dsu[x] == x ? x : dsu[x] = find(dsu[x]); }
int query(int u, int v){ // cạnh lớn nhất trên đường đi u - v trong cây
int best = 0;
if(dep[u] < dep[v]) swap(u, v);
int d = dep[u] - dep[v];
for(int k = 0; k < LOG; k++)
if(d >> k & 1){ best = max(best, mx[k][u]); u = up[k][u]; }
if(u == v) return best;
for(int k = LOG - 1; k >= 0; k--)
if(up[k][u] != up[k][v]){
best = max({best, mx[k][u], mx[k][v]});
u = up[k][u]; v = up[k][v];
}
return max({best, mx[0][u], mx[0][v]});
}
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> m >> q;
vector<array<int, 3>> E(m);
for(auto &e : E) cin >> e[1] >> e[2] >> e[0]; // (w, u, v)
sort(E.begin(), E.end());
for(int i = 1; i <= n; i++) dsu[i] = i;
for(auto &e : E){ // Kruskal: cây khung nhỏ nhất
int a = find(e[1]), b = find(e[2]);
if(a == b) continue;
dsu[a] = b;
adj[e[1]].push_back({e[2], e[0]}); adj[e[2]].push_back({e[1], e[0]});
}
vector<int> order = {1};
vector<bool> seen(n + 1, false);
seen[1] = true; up[0][1] = 1;
for(int i = 0; i < (int)order.size(); i++){
int u = order[i];
for(auto [v, w] : adj[u]) if(!seen[v]){
seen[v] = true; up[0][v] = u; mx[0][v] = w; dep[v] = dep[u] + 1;
order.push_back(v);
}
}
for(int k = 1; k < LOG; k++)
for(int v = 1; v <= n; v++){
int mid = up[k - 1][v];
up[k][v] = up[k - 1][mid];
mx[k][v] = max(mx[k - 1][v], mx[k - 1][mid]);
}
while(q--){
int u, v; cin >> u >> v;
cout << query(u, v) << "\n";
}
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n, m, q = int(data[0]), int(data[1]), int(data[2])
p = 3
E = []
for _ in range(m):
u, v, w = int(data[p]), int(data[p + 1]), int(data[p + 2]); p += 3
E.append((w, u, v))
E.sort()
dsu = list(range(n + 1))
def find(x):
while dsu[x] != x:
dsu[x] = dsu[dsu[x]]
x = dsu[x]
return x
adj = [[] for _ in range(n + 1)]
for w, u, v in E: # Kruskal: cây khung nhỏ nhất
a, b = find(u), find(v)
if a != b:
dsu[a] = b
adj[u].append((v, w)); adj[v].append((u, w))
LOG = max(1, n.bit_length())
par = [0] * (n + 1); m0 = [0] * (n + 1); dep = [0] * (n + 1); par[1] = 1
seen = [False] * (n + 1); seen[1] = True
order = [1]
for u in order:
for v, w in adj[u]:
if not seen[v]:
seen[v] = True; par[v] = u; m0[v] = w; dep[v] = dep[u] + 1
order.append(v)
up, mx = [par], [m0]
for k in range(1, LOG):
pu, pm = up[-1], mx[-1]
up.append([pu[pu[v]] for v in range(n + 1)])
mx.append([max(pm[v], pm[pu[v]]) for v in range(n + 1)])
def query(u, v):
best = 0
if dep[u] < dep[v]:
u, v = v, u
d, k = dep[u] - dep[v], 0
while d:
if d & 1:
best = max(best, mx[k][u]); u = up[k][u]
d >>= 1; k += 1
if u == v:
return best
for k in range(LOG - 1, -1, -1):
if up[k][u] != up[k][v]:
best = max(best, mx[k][u], mx[k][v])
u = up[k][u]; v = up[k][v]
return max(best, mx[0][u], mx[0][v])
out = []
for _ in range(q):
u, v = int(data[p]), int(data[p + 1]); p += 2
out.append(query(u, v))
print('\n'.join(map(str, out)))
main()Ba bạn đang ở ba đỉnh $a, b, c$ của một cây $n$ đỉnh ($n, q \le 2 \cdot 10^5$, mỗi cạnh dài 1). Họ muốn chọn một đỉnh $x$ để gặp nhau sao cho tổng quãng đường ba người đi là nhỏ nhất. Với mỗi truy vấn $a, b, c$, in ra đỉnh $x$ (đảm bảo duy nhất) và tổng quãng đường nhỏ nhất.
Input: dòng đầu $n, q$; $n - 1$ dòng tiếp là các cạnh; $q$ dòng sau mỗi dòng $a, b, c$.
12 3
1 2
1 3
2 4
2 5
3 6
4 7
4 8
5 9
6 10
7 11
11 12
12 8 9
10 9 3
5 5 54 7
3 6
5 0📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200005, LOG = 18;
int n, q, up[LOG][MAXN], dep[MAXN];
vector<int> adj[MAXN];
int lca(int u, int v){
if(dep[u] < dep[v]) swap(u, v);
int d = dep[u] - dep[v];
for(int k = 0; k < LOG; k++)
if(d >> k & 1) u = up[k][u];
if(u == v) return u;
for(int k = LOG - 1; k >= 0; k--)
if(up[k][u] != up[k][v]){ u = up[k][u]; v = up[k][v]; }
return up[0][u];
}
int dist(int u, int v){ return dep[u] + dep[v] - 2 * dep[lca(u, v)]; }
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> q;
for(int i = 1; i < n; i++){
int u, v; cin >> u >> v;
adj[u].push_back(v); adj[v].push_back(u);
}
vector<int> order = {1};
vector<bool> seen(n + 1, false);
seen[1] = true; up[0][1] = 1;
for(int i = 0; i < (int)order.size(); i++){
int u = order[i];
for(int v : adj[u]) if(!seen[v]){
seen[v] = true; up[0][v] = u; dep[v] = dep[u] + 1;
order.push_back(v);
}
}
for(int k = 1; k < LOG; k++)
for(int v = 1; v <= n; v++)
up[k][v] = up[k - 1][up[k - 1][v]];
while(q--){
int a, b, c; cin >> a >> b >> c;
int x = lca(a, b), y = lca(b, c), z = lca(a, c);
int best = x; // điểm hẹn = LCA sâu nhất trong ba cặp
if(dep[y] > dep[best]) best = y;
if(dep[z] > dep[best]) best = z;
long long s = (long long)dist(a, b) + dist(b, c) + dist(a, c);
cout << best << " " << s / 2 << "\n";
}
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n, q = int(data[0]), int(data[1])
adj = [[] for _ in range(n + 1)]
p = 2
for _ in range(n - 1):
u, v = int(data[p]), int(data[p + 1]); p += 2
adj[u].append(v); adj[v].append(u)
LOG = max(1, n.bit_length())
par = [0] * (n + 1); dep = [0] * (n + 1); par[1] = 1
seen = [False] * (n + 1); seen[1] = True
order = [1]
for u in order:
for v in adj[u]:
if not seen[v]:
seen[v] = True; par[v] = u; dep[v] = dep[u] + 1
order.append(v)
up = [par]
for k in range(1, LOG):
prev = up[-1]
up.append([prev[prev[v]] for v in range(n + 1)])
def lca(u, v):
if dep[u] < dep[v]:
u, v = v, u
d, k = dep[u] - dep[v], 0
while d:
if d & 1:
u = up[k][u]
d >>= 1; k += 1
if u == v:
return u
for k in range(LOG - 1, -1, -1):
if up[k][u] != up[k][v]:
u = up[k][u]; v = up[k][v]
return up[0][u]
def dist(u, v):
return dep[u] + dep[v] - 2 * dep[lca(u, v)]
out = []
for _ in range(q):
a, b, c = int(data[p]), int(data[p + 1]), int(data[p + 2]); p += 3
best = max((lca(a, b), lca(b, c), lca(a, c)), key=lambda x: dep[x]) # LCA sâu nhất
s = dist(a, b) + dist(b, c) + dist(a, c)
out.append('%d %d' % (best, s // 2))
print('\n'.join(out))
main()Cho cây $n$ đỉnh ($n \le 2 \cdot 10^5$) và $m$ đường đi ($m \le 2 \cdot 10^5$), đường đi thứ $i$ nối $u_i$ với $v_i$ (có thể $u_i = v_i$). Với mỗi đỉnh, đếm xem có bao nhiêu đường đi đi qua nó (tính cả hai đầu mút).
Input: dòng đầu $n, m$; $n - 1$ dòng tiếp là các cạnh; $m$ dòng sau mỗi dòng $u_i, v_i$. Output: $n$ số trên một dòng.
12 3
1 2
1 3
2 4
2 5
3 6
4 7
4 8
5 9
6 10
7 11
11 12
12 9
10 8
6 61 2 1 2 1 2 1 1 1 1 1 1📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
cnt trong cây con của $x$. Với đường đi $u$ – $v$ có $l = $ LCA(u, v): tăng cnt[u] và cnt[v] thêm 1, giảm cnt[l] đi 1 và giảm cnt[cha(l)] đi 1 (nếu $l$ không phải gốc). Thử kiểm tra: mỗi đỉnh trên đường đi nhận đúng +1, các đỉnh khác nhận 0. Cuối cùng cộng dồn từ lá lên gốc: duyệt các đỉnh theo thứ tự BFS ngược, cộng giá trị của con vào cha. Tổng $O((n + m) \log n)$.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200005, LOG = 18;
int n, q, up[LOG][MAXN], dep[MAXN];
vector<int> adj[MAXN];
long long cnt[MAXN];
int lca(int u, int v){
if(dep[u] < dep[v]) swap(u, v);
int d = dep[u] - dep[v];
for(int k = 0; k < LOG; k++)
if(d >> k & 1) u = up[k][u];
if(u == v) return u;
for(int k = LOG - 1; k >= 0; k--)
if(up[k][u] != up[k][v]){ u = up[k][u]; v = up[k][v]; }
return up[0][u];
}
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> q;
for(int i = 1; i < n; i++){
int u, v; cin >> u >> v;
adj[u].push_back(v); adj[v].push_back(u);
}
vector<int> order = {1};
vector<bool> seen(n + 1, false);
seen[1] = true; up[0][1] = 1;
for(int i = 0; i < (int)order.size(); i++){
int u = order[i];
for(int v : adj[u]) if(!seen[v]){
seen[v] = true; up[0][v] = u; dep[v] = dep[u] + 1;
order.push_back(v);
}
}
for(int k = 1; k < LOG; k++)
for(int v = 1; v <= n; v++)
up[k][v] = up[k - 1][up[k - 1][v]];
while(q--){ // q đường đi
int u, v; cin >> u >> v;
int l = lca(u, v);
cnt[u]++; cnt[v]++; cnt[l]--; // đánh dấu hiệu trên cây
if(l != 1) cnt[up[0][l]]--;
}
for(int i = n - 1; i > 0; i--) // cộng dồn từ lá lên (BFS ngược)
cnt[up[0][order[i]]] += cnt[order[i]];
for(int v = 1; v <= n; v++) cout << cnt[v] << " ";
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n, q = int(data[0]), int(data[1])
adj = [[] for _ in range(n + 1)]
p = 2
for _ in range(n - 1):
u, v = int(data[p]), int(data[p + 1]); p += 2
adj[u].append(v); adj[v].append(u)
LOG = max(1, n.bit_length())
par = [0] * (n + 1); dep = [0] * (n + 1); par[1] = 1
seen = [False] * (n + 1); seen[1] = True
order = [1]
for u in order:
for v in adj[u]:
if not seen[v]:
seen[v] = True; par[v] = u; dep[v] = dep[u] + 1
order.append(v)
up = [par]
for k in range(1, LOG):
prev = up[-1]
up.append([prev[prev[v]] for v in range(n + 1)])
def lca(u, v):
if dep[u] < dep[v]:
u, v = v, u
d, k = dep[u] - dep[v], 0
while d:
if d & 1:
u = up[k][u]
d >>= 1; k += 1
if u == v:
return u
for k in range(LOG - 1, -1, -1):
if up[k][u] != up[k][v]:
u = up[k][u]; v = up[k][v]
return up[0][u]
cnt = [0] * (n + 1)
for _ in range(q): # q đường đi
u, v = int(data[p]), int(data[p + 1]); p += 2
l = lca(u, v)
cnt[u] += 1; cnt[v] += 1; cnt[l] -= 1
if l != 1:
cnt[par[l]] -= 1
for i in range(n - 1, 0, -1): # cộng dồn từ lá lên (BFS ngược)
x = order[i]
cnt[par[x]] += cnt[x]
print(*cnt[1:])
main()
- Không biết học gì trước, học gì sau, học lan man nên kiến thức bị hổng.
- Bí bài không ai gỡ, ngồi cả buổi vẫn không ra rồi bỏ cuộc.
- Code chạy được nhưng không đủ điểm, không biết sai ở đâu, chậm ở đâu.
- Không có đề thi thử và người chấm, nên không biết mình đang ở mức nào.
- Dễ nản giữa chừng khi không có ai theo sát.
- Lộ trình 111 buổi video sắp sẵn từ dòng code đầu tiên đến đề HSG thật của các tỉnh.
- Thầy trực tiếp gỡ bí, chữa bài cho từng em qua nhóm Zalo riêng.
- Hệ thống chấm bài tự động 24/7 và thi thử HSG hằng tuần để biết chính xác mình đang ở đâu.
- Đóng học phí một lần, thầy kèm lâu dài: từ thi chuyên Tin đến HSG quốc gia và cả khi lên đại học.
Nhận xét
Đăng nhận xét