Bài 44: Kỹ thuật trên cây trong C++ và Python: Euler tour kết hợp Fenwick, gộp tập nhỏ vào lớn (small-to-large) và DSU on tree
Lời mở đầu
Ở bài 33 em đã tính kích thước cây con, quy hoạch động trên cây bằng một lần DFS. Ở bài 34 em gặp mảng tin/tout để kiểm tra tổ tiên trong $O(1)$. Nhưng đề thi HSG còn thích hai kiểu câu hỏi khó hơn: (1) cây thay đổi liên tục (sửa giá trị một đỉnh, cộng thêm cho cả một phòng ban…) xen kẽ với câu hỏi “tổng của cả cây con là bao nhiêu?”; (2) mỗi cây con phải trả lời một câu hỏi về cả tập hợp các giá trị bên trong: có bao nhiêu màu khác nhau, màu nào xuất hiện nhiều nhất, có bao nhiêu cặp đỉnh cách nhau đúng $K$…
Hôm nay ta học hai kỹ thuật “đinh” cho hai kiểu đó. Euler tour duỗi cây thành một mảng, cây con nào cũng thành một đoạn liên tiếp, và thế là Fenwick, Segment Tree (bài 31), lazy (bài 37) dùng được ngay trên cây. Gộp tập nhỏ vào lớn (small-to-large, còn gọi là DSU on tree) là phiên bản trên cây của ý tưởng “hợp theo kích thước” của DSU (bài 30): luôn đổ tập nhỏ hơn vào tập lớn hơn, nhờ đó mỗi phần tử chỉ bị chép $O(\log n)$ lần.
tin, tout, mảng ord để biến mỗi cây con thành đoạn liên tiếp; dùng Fenwick trên Euler tour để sửa một đỉnh và hỏi tổng cây con, cộng cho cả cây con, hỏi tổng trên đường gốc – đỉnh; bài toán đếm số màu khác nhau trong mỗi cây con và vì sao gộp ngây thơ tốn $O(n^2)$; kỹ thuật gộp tập nhỏ vào lớn với chứng minh $O(n \log^2 n)$ và mẹo swap trong $O(1)$; biến thể sack (DSU on tree với con nặng) chạy $O(n \log n)$ và chuyện đệ quy sâu. Có 2 khung chạy tay, 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 1Euler tour: biến cây con thành đoạn liên tiếp
Nhắc lại từ bài 34: DFS từ gốc với một bộ đếm timer. Khi vào đỉnh $u$, tăng bộ đếm và ghi tin[u] = timer; khi rời $u$ (đã đi hết cây con), ghi tout[u] = timer. Hôm nay ta thêm một mảng nữa: ord[t] = đỉnh được thăm thứ $t$, tức là ord[tin[u]] = u. Mảng ord chính là cái cây đã được duỗi thẳng ra.
Điều quan trọng nhất: DFS vào $u$ rồi đi hết cây con của $u$ mới rời $u$, nên trong khoảng thời gian đó nó chỉ thăm các đỉnh của cây con $u$, và thăm tất cả chúng. Vì vậy:
ord[tin[u]], ord[tin[u] + 1], …, ord[tout[u]] · kích thước = tout[u] − tin[u] + 1Hình 1. Cây ví dụ dùng xuyên suốt bài (gốc 1, DFS thăm con theo số tăng dần). Dưới mỗi đỉnh là đoạn $[\text{tin}, \text{tout}]$. Cây con của 2 (vàng và xanh lá) là đoạn [2, 6].
| t | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| ord[t] | 1 | 2 | 4 | 5 | 8 | 9 | 3 | 6 | 7 | 10 |
| a[ord[t]] | 5 | 3 | 7 | 1 | 2 | 8 | 2 | 4 | 6 | 9 |
Bảng 1. Mảng ord của cây Hình 1 và giá trị a của từng đỉnh xếp theo ord. Các ô tô màu là cây con của 2: {2, 4, 5, 8, 9}, nằm liền nhau từ ô 2 tới ô 6. Tổng cây con của 2 bằng tổng đoạn này: 21.
Em bấm Tiếp để xem bộ đếm chạy và mỗi khi DFS rời một đỉnh, cả cây con của đỉnh đó sáng lên thành một đoạn liền trên mảng ord. Thử đổi dãy cha để thấy tính chất này đúng với mọi cây:
void dfs(int u, int p){
tin[u] = ++timer_; ord_[timer_] = u; // vào u
for(int v : adj[u]) if(v != p) dfs(v, u);
tout[u] = timer_; // rời u
}
// cây con u <=> đoạn [tin[u], tout[u]] trên mảng ord_
// v thuộc cây con u <=> tin[u] <= tin[v] <= tout[u]Phần 2Fenwick trên Euler tour: sửa đỉnh, hỏi tổng cây con
Bài toán. Cây $n$ đỉnh gốc 1, đỉnh $u$ có giá trị $a_u$. Có $q$ truy vấn ($n, q \le 2 \cdot 10^5$): 1 u x gán $a_u = x$; 2 u in tổng giá trị các đỉnh trong cây con của $u$. Duyệt cây con mỗi lần tốn $O(n)$, tổng $O(nq)$, quá chậm.
Cách làm. Đặt giá trị của đỉnh $u$ vào ô tin[u] của một mảng $b$: $b[\text{tin}[u]] = a_u$. Khi đó:
- sửa giá trị đỉnh $u$ = sửa một ô $b[\text{tin}[u]]$;
- tổng cây con của $u$ = tổng đoạn $b[\text{tin}[u] .. \text{tout}[u]]$ = $\text{sum}(\text{tout}[u]) - \text{sum}(\text{tin}[u] - 1)$.
Đúng bài toán “sửa một phần tử, hỏi tổng đoạn” của bài 31. Một cây Fenwick giải mỗi thao tác trong $O(\log n)$. Ví dụ với Bảng 1: cây con của 2 là đoạn [2, 6], tổng $3 + 7 + 1 + 2 + 8 = 21$. Gán $a_5 = 10$ (tăng 9) thì chỉ ô $b[\text{tin}[5]] = b[4]$ đổi, và tổng cây con của 2 thành 30, của gốc thành 56.
Xem code C++ / Python: euler tour + fenwick: gán giá trị đỉnh, tổng cây con (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200005;
int n, q, tin[MAXN], tout[MAXN], timer_ = 0;
long long a[MAXN], bit[MAXN];
vector<int> adj[MAXN];
void add(int i, long long v){ for(; i <= n; i += i & -i) bit[i] += v; }
long long sum(int i){ long long s = 0; for(; i > 0; i -= i & -i) s += bit[i]; return s; }
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> q;
for(int i = 1; i <= n; i++) cin >> a[i];
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> par(n + 1, 0), it(n + 1, 0), st = {1}; // DFS không đệ quy
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_; // vào v
st.push_back(v);
} else {
tout[u] = timer_; // rời u
st.pop_back();
}
}
for(int u = 1; u <= n; u++) add(tin[u], a[u]); // giá trị của u nằm ở ô tin[u]
while(q--){
int t, u; cin >> t >> u;
if(t == 1){
long long x; cin >> x;
add(tin[u], x - a[u]); a[u] = x; // gán a[u] = x
} else {
cout << sum(tout[u]) - sum(tin[u] - 1) << "\n"; // tổng đoạn [tin, tout]
}
}
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n, q = int(data[0]), int(data[1])
a = [0] + [int(x) for x in data[2:2 + n]]
pos = 2 + n
adj = [[] for _ in range(n + 1)]
for _ in range(n - 1):
u, v = int(data[pos]), int(data[pos + 1]); pos += 2
adj[u].append(v); adj[v].append(u)
tin = [0] * (n + 1); tout = [0] * (n + 1); par = [0] * (n + 1); it = [0] * (n + 1)
timer = 1; tin[1] = 1; st = [1] # DFS không đệ quy
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 # vào v
st.append(v)
else:
tout[u] = timer # rời u
st.pop()
bit = [0] * (n + 1)
def add(i, v):
while i <= n:
bit[i] += v; i += i & -i
def pref(i):
s = 0
while i > 0:
s += bit[i]; i -= i & -i
return s
for u in range(1, n + 1):
add(tin[u], a[u]) # giá trị của u nằm ở ô tin[u]
out = []
for _ in range(q):
t, u = int(data[pos]), int(data[pos + 1]); pos += 2
if t == 1:
x = int(data[pos]); pos += 1
add(tin[u], x - a[u]); a[u] = x # gán a[u] = x
else:
out.append(pref(tout[u]) - pref(tin[u] - 1))
print('\n'.join(map(str, out)))
main()Khung chạy tay dưới đây dùng DFS đệ quy cho dễ đọc. Em bấm Tự chạy để thấy tin, tout được ghi, rồi mỗi truy vấn cây con chỉ còn là hai lần tính tổng tiền tố trên Fenwick:
Để nhìn rõ hơn vì sao chỉ cần hai lần tính tổng tiền tố, em dùng mô phỏng sau: đỉnh $u$ cần hỏi tô vàng, cả cây con tô xanh lá, các ô bit được cộng lần lượt sáng lên. Thử đổi $u$ thành 3, 5 hoặc 1:
Ba biến thể hay gặp. Cùng một mảng Euler tour, chỉ đổi cách dùng Fenwick là trả lời được những truy vấn khác:
| Cập nhật | Truy vấn | Làm trên Fenwick | Vì sao đúng |
|---|---|---|---|
| $a_u$ += x (một đỉnh) | tổng cây con $u$ | add(tin[u], x); hỏi sum(tout) − sum(tin − 1) | cây con = đoạn |
| cộng x cho cả cây con $u$ | giá trị đỉnh $v$ | add(tin[u], x), add(tout[u] + 1, −x); hỏi sum(tin[v]) | mảng hiệu: cộng đoạn, hỏi một điểm |
| $a_u$ += x (một đỉnh) | tổng trên đường gốc → $v$ | add(tin[u], x), add(tout[u] + 1, −x); hỏi sum(tin[v]) | $u$ nằm trên đường gốc → $v$ ⇔ $v$ thuộc cây con $u$ |
| cộng x cho cả cây con | tổng cây con | Segment Tree lazy (bài 37) trên đoạn [tin, tout] | cộng đoạn, hỏi tổng đoạn |
Bảng 2. Các dạng truy vấn cây con / đường đi về gốc và cách quy về bài toán trên mảng.
Dòng thứ ba đáng để em suy nghĩ kỹ, vì nó “lật ngược” vai trò: đỉnh $u$ có mặt trên đường từ gốc tới $v$ khi và chỉ khi $u$ là tổ tiên của $v$, tức là $v$ nằm trong cây con của $u$, tức là $\text{tin}[v] \in [\text{tin}[u], \text{tout}[u]]$. Vậy “thêm $x$ vào đỉnh $u$” tương đương “cộng $x$ cho mọi ô thuộc đoạn $[\text{tin}[u], \text{tout}[u]]$”, còn “tổng trên đường gốc → $v$” là giá trị tại một điểm $\text{tin}[v]$. Kết hợp với LCA (bài 34), tổng trên đường đi $u$ – $v$ bất kỳ là $S(u) + S(v) - S(l) - S(\text{cha}(l))$ với $l = \text{LCA}(u, v)$ và $S(x)$ là tổng trên đường gốc → $x$.
add(u, x) thay vì add(tin[u], x) là lỗi kinh điển, test nhỏ có khi vẫn đúng vì tin trùng số hiệu. 2. add(tout[u] + 1, −x) có thể chạm ô $n + 1$: hàm add với điều kiện i <= n tự bỏ qua, nhưng nếu em dùng mảng hiệu thường thì phải khai báo dư một ô. 3. Tổng có thể vượt $2^{31}$: dùng long long.Phần 3Đếm số màu khác nhau trong mỗi cây con
Bài toán. Cây $n$ đỉnh gốc 1 ($n \le 2 \cdot 10^5$), đỉnh $u$ có màu $c_u$. Với mọi đỉnh $u$, đếm xem cây con của $u$ có bao nhiêu màu khác nhau. Với cây Hình 1 và màu $c = (1, 2, 1, 3, 2, 3, 1, 2, 1, 3)$ của các đỉnh 1..10, đáp án là $3, 3, 2, 1, 2, 1, 2, 1, 1, 1$.
Tổng thì cộng dồn được (tổng cây con = $a_u$ + tổng các cây con của con), còn “số màu khác nhau” thì không: cây con 2 có 3 màu, cây con 3 có 2 màu, nhưng gốc không có $1 + 3 + 2$ màu mà chỉ có 3, vì hai bên có thể trùng màu. Muốn ghép, ta phải biết cụ thể tập màu của từng cây con.
Cách 1: DFS riêng cho từng đỉnh. Với mỗi $u$, duyệt cả cây con, bỏ màu vào một set. Tổng công việc = tổng kích thước các cây con = tổng độ sâu, với cây đường thẳng là $1 + 2 + \cdots + n \approx n^2 / 2 = 2 \cdot 10^{10}$. Quá chậm.
Cách 2: gộp ngây thơ từ dưới lên. Duyệt từ lá lên gốc, S[u] = {c[u]} rồi chép hết S[con] vào S[u]. Nghe hợp lý, nhưng trên cây đường thẳng 1 – 2 – … – n, tập của đỉnh $n$ có 1 phần tử được chép lên $n - 1$, tập có 2 phần tử được chép lên $n - 2$… Tổng số lần chép vẫn là $\frac{n(n - 1)}{2}$, nhân thêm $\log n$ cho mỗi lần chèn vào set. Cái dở nằm ở chỗ: tập to của con cứ bị chép đi chép lại sang tập bé xíu của cha.
Hình 2. Cây đường thẳng 6 đỉnh, gộp từ đỉnh 6 lên đỉnh 1. Gộp ngây thơ chép tập của con (5, 4, 3, 2, 1 phần tử) sang cha. Nếu thay vào đó ta giữ lại tập to của con và chỉ chép 1 màu của cha sang, mỗi bước chỉ tốn 1.
Phần 4Gộp tập nhỏ vào lớn (small-to-large)
Sửa cách 2 đúng một dòng: khi gộp hai tập, luôn chép tập nhỏ hơn vào tập lớn hơn. Nếu tập của con lớn hơn tập của cha, ta đổi chỗ hai tập trước rồi mới chép. Điều kỳ diệu là việc đổi chỗ không tốn gì: swap(S[u], S[v]) giữa hai std::set chỉ đổi con trỏ bên trong, chạy $O(1)$ (trong Python thì chỉ đổi hai tham chiếu).
Chứng minh $O(n \log n)$ lần chép. Theo dõi một phần tử $x$ bất kỳ. Mỗi lần $x$ bị chép, nó đi từ tập nhỏ (cỡ $s$) sang tập lớn (cỡ $\ge s$), nên tập chứa $x$ sau đó có cỡ $\ge 2s$: ít nhất gấp đôi. Một tập không thể lớn hơn $n$, nên $x$ bị chép không quá $\log_2 n$ lần. Có $n$ phần tử, tổng số lần chép $\le n \log_2 n$. Mỗi lần chép là một lần chèn vào set tốn $O(\log n)$, vậy tổng cộng $O(n \log^2 n)$. Với unordered_set hoặc set của Python (bảng băm) thì còn $O(n \log n)$ trung bình.
Lập luận này giống hệt lập luận “hợp theo kích thước” của DSU ở bài 30. Em xem mô phỏng: mỗi đỉnh mang một phần tử riêng, số dưới mỗi đỉnh đếm số lần phần tử đó bị chép. Thử nhập cây đường thẳng 1 2 3 4 5 6 7 8 9 10 để so tổng số lần chép với gộp ngây thơ:
Cài đặt không đệ quy. Để tránh đệ quy sâu, ta BFS lấy thứ tự các đỉnh (cha luôn đứng trước con), rồi duyệt ngược thứ tự đó: tới lượt $u$ thì mọi con của $u$ đã được gộp vào S[u], ta ghi đáp án ans[u] = |S[u]| rồi gộp S[u] lên cha theo quy tắc nhỏ vào lớn.
Xem code C++ / Python: đếm số màu khác nhau trong mỗi cây con bằng gộp nhỏ vào lớn (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200005;
int n, c[MAXN], par[MAXN], ans[MAXN];
vector<int> adj[MAXN];
set<int> S[MAXN];
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n;
for(int i = 1; i <= n; i++) cin >> c[i];
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: cha đứng trước con
vector<bool> seen(n + 1, false); seen[1] = true;
for(int i = 0; i < (int)order.size(); i++)
for(int v : adj[order[i]]) if(!seen[v]){
seen[v] = true; par[v] = order[i]; order.push_back(v);
}
for(int u = 1; u <= n; u++) S[u].insert(c[u]);
for(int i = n - 1; i >= 0; i--){ // con được xử lý trước cha
int u = order[i];
ans[u] = S[u].size(); // mọi con của u đã gộp vào S[u]
int p = par[u];
if(p == 0) continue;
if(S[u].size() > S[p].size()) swap(S[u], S[p]); // O(1): chỉ đổi “ruột” hai set
for(int x : S[u]) S[p].insert(x); // đổ tập NHỎ vào tập LỚN
S[u].clear();
}
for(int u = 1; u <= n; u++) cout << ans[u] << " ";
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0])
c = [0] + [int(x) for x in data[1:1 + n]]
adj = [[] for _ in range(n + 1)]
pos = 1 + n
for _ in range(n - 1):
u, v = int(data[pos]), int(data[pos + 1]); pos += 2
adj[u].append(v); adj[v].append(u)
par = [0] * (n + 1); seen = [False] * (n + 1); seen[1] = True
order = [1] # BFS: cha đứng trước con
for u in order:
for v in adj[u]:
if not seen[v]:
seen[v] = True; par[v] = u; order.append(v)
S = [None] + [{c[u]} for u in range(1, n + 1)]
ans = [0] * (n + 1)
for u in reversed(order): # con được xử lý trước cha
ans[u] = len(S[u])
p = par[u]
if p == 0:
continue
small, big = S[u], S[p]
if len(small) > len(big):
small, big = big, small # chỉ đổi tham chiếu, O(1)
big.update(small) # đổ tập NHỎ vào tập LỚN
S[p] = big; S[u] = None
print(*ans[1:])
main()Bản đệ quy thì gọn và dễ hiểu hơn, em xem từng dòng trong khung chạy tay. Để ý dòng swap: có lúc tập của con to hơn và hai tập được đổi chỗ, sau đó chỉ vài màu được chép:
// S[u] đã chứa thông tin của u, S[v] là thông tin cả cây con v
if(S[v].size() > S[u].size()) swap(S[u], S[v]); // O(1)
for(auto x : S[v]){
// (nếu cần) dùng x để cập nhật đáp án với S[u] TRƯỚC khi chèn
S[u].insert(x);
}
S[v].clear();set bằng map<màu, số lần> là đếm được màu xuất hiện nhiều nhất (bài tập 5); thay bằng map<độ sâu, số đỉnh> là đếm được cặp đỉnh cách nhau $K$ (bài tập 8).S[u] = S[v] là sao chép cả tập, tốn $O(|S[v]|)$, mất hết tác dụng. Phải dùng swap (hoặc mảng con trỏ / chỉ số). 2. Ghi đáp án quá muộn: sau khi gộp lên cha, S[v] bị xoá hoặc bị đổi chỗ, nên đáp án của $v$ phải ghi trước khi gộp. Vì thế bài toán thường phải giải offline (đọc hết rồi mới trả lời). 3. So sánh sai thứ: phải so kích thước tập, không phải kích thước cây con hay số hiệu đỉnh. (So kích thước cây con cũng đúng độ phức tạp, nhưng so kích thước tập thì đơn giản và an toàn hơn.)Phần 5Sack (DSU on tree) với con nặng: O(n log n)
Small-to-large dùng set/map nên có thêm một thừa số $\log$ và tốn bộ nhớ cấp phát. Khi màu nhỏ ($c_u \le n$), ta có thể dùng một mảng đếm toàn cục cnt[màu] cùng biến distinct (số màu đang có cnt > 0), và tổ chức thứ tự duyệt thật khéo. Đó là kỹ thuật sack (có nơi gọi là DSU on tree):
- Gọi con nặng
big[u]là con có cây con lớn nhất; các con còn lại là con nhẹ. dfs(u, keep): (1) gọi đệ quy mọi con nhẹ vớikeep = false: tính xong đáp án của chúng rồi xoá sạch khỏicnt; (2) gọi con nặng vớikeep = true: tính xong và giữ nguyên dữ liệu trongcnt; (3) thêm $u$ và toàn bộ các cây con nhẹ vàocnt, duyệt nhanh nhờ Euler tourord[tin[v]..tout[v]]; (4) ghians[u] = distinct; (5) nếukeep = falsethì xoá cả cây con $u$.
Vì sao $O(n \log n)$? Một đỉnh $x$ bị thêm lại (bước 3) mỗi khi nó nằm trong một cây con nhẹ của một tổ tiên. Đi từ $x$ lên gốc, mỗi lần đi qua một cạnh nhẹ (từ con nhẹ lên cha) thì kích thước cây con ít nhất gấp đôi (vì con nặng còn to hơn con nhẹ). Vậy có không quá $\log_2 n$ cạnh nhẹ trên đường lên gốc, và $x$ bị thêm/xoá $O(\log n)$ lần. Mỗi lần thêm/xoá là $O(1)$ trên mảng, tổng $O(n \log n)$. Lại là lập luận “gấp đôi” quen thuộc!
| Đỉnh u | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| kích thước cây con | 10 | 5 | 4 | 1 | 3 | 1 | 2 | 1 | 1 | 1 |
| con nặng big[u] | 2 | 5 | 7 | – | 8 | – | 10 | – | – | – |
Bảng 3. Con nặng của từng đỉnh trong cây Hình 1 (hai con bằng nhau thì chọn con thăm trước). Ví dụ ở gốc 1: cây con 2 có 5 đỉnh, cây con 3 có 4 đỉnh nên con nặng là 2; khi tính gốc, chỉ phải thêm lại 4 đỉnh của cây con nhẹ.
Xem code C++ / Python: sack (dsu on tree) đếm số màu khác nhau (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200005;
int n, c[MAXN], sz[MAXN], big[MAXN], tin[MAXN], tout[MAXN], ord_[MAXN], timer_ = 0;
int cnt[MAXN], distinct_ = 0, ans[MAXN];
vector<int> adj[MAXN];
void prep(int u, int p){ // sz, con nặng, tin/tout, ord
sz[u] = 1; tin[u] = ++timer_; ord_[timer_] = u; big[u] = 0;
for(int v : adj[u]) if(v != p){
prep(v, u);
sz[u] += sz[v];
if(big[u] == 0 || sz[v] > sz[big[u]]) big[u] = v;
}
tout[u] = timer_;
}
void addV(int v){ if(cnt[c[v]]++ == 0) distinct_++; }
void delV(int v){ if(--cnt[c[v]] == 0) distinct_--; }
void dfs(int u, int p, bool keep){
for(int v : adj[u]) if(v != p && v != big[u]) dfs(v, u, false); // con nhẹ: làm xong rồi xoá
if(big[u]) dfs(big[u], u, true); // con nặng: giữ lại cnt
addV(u);
for(int v : adj[u]) if(v != p && v != big[u])
for(int t = tin[v]; t <= tout[v]; t++) addV(ord_[t]); // thêm lại các cây con nhẹ
ans[u] = distinct_;
if(!keep)
for(int t = tin[u]; t <= tout[u]; t++) delV(ord_[t]); // xoá sạch cây con u
}
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n;
for(int i = 1; i <= n; i++) cin >> c[i];
for(int i = 1; i < n; i++){
int u, v; cin >> u >> v;
adj[u].push_back(v); adj[v].push_back(u);
}
prep(1, 0);
dfs(1, 0, true);
for(int u = 1; u <= n; u++) cout << ans[u] << " ";
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0])
c = [0] + [int(x) for x in data[1:1 + n]]
adj = [[] for _ in range(n + 1)]
pos = 1 + n
for _ in range(n - 1):
u, v = int(data[pos]), int(data[pos + 1]); pos += 2
adj[u].append(v); adj[v].append(u)
# DFS không đệ quy: tin, tout, ord (thứ tự vào), cha
par = [0] * (n + 1); tin = [0] * (n + 1); tout = [0] * (n + 1); it = [0] * (n + 1)
order = [0, 1]; tin[1] = 1; st = [1]
while st:
u = st[-1]
if it[u] < len(adj[u]):
v = adj[u][it[u]]; it[u] += 1
if v != par[u]:
par[v] = u; tin[v] = len(order); order.append(v); st.append(v)
else:
tout[u] = len(order) - 1; st.pop()
sz = [1] * (n + 1); big = [0] * (n + 1)
for t in range(n, 1, -1): # duyệt ngược thứ tự vào: con trước cha
v = order[t]; p = par[v]
sz[p] += sz[v]
if big[p] == 0 or sz[v] > sz[big[p]]:
big[p] = v
cpos = [c[v] for v in order] # cpos[t] = màu của đỉnh ord[t]
cnt = [0] * (n + 1); ans = [0] * (n + 1); distinct = 0
stack = [(1, True, False)] # (đỉnh, keep, đã xử lý các con chưa)
while stack:
u, keep, done = stack.pop()
if not done:
stack.append((u, keep, True))
if big[u]:
stack.append((big[u], True, False)) # con nặng làm SAU các con nhẹ
for v in adj[u]:
if v != par[u] and v != big[u]:
stack.append((v, False, False))
continue
cols = [c[u]]
for v in adj[u]:
if v != par[u] and v != big[u]:
cols += cpos[tin[v]:tout[v] + 1] # cả cây con nhẹ v là một đoạn
for col in cols:
if cnt[col] == 0:
distinct += 1
cnt[col] += 1
ans[u] = distinct
if not keep:
for col in cpos[tin[u]:tout[u] + 1]:
cnt[col] -= 1
if cnt[col] == 0:
distinct -= 1
print(*ans[1:])
main()(u, keep, đã_xử_lý_con), đẩy con nặng vào trước các con nhẹ để con nhẹ được lấy ra và làm xong trước. Khi không chắc về máy chấm, em làm giống bản Python, hoặc dùng cách gộp nhỏ vào lớn theo thứ tự BFS ngược như phần 4.| Cách làm | Thời gian | Bộ nhớ | Ưu điểm | Dùng khi |
|---|---|---|---|---|
| DFS từng đỉnh | $O(n^2)$ | $O(n)$ | dễ viết | $n \le 5000$, để đối chiếu |
| Euler tour + Fenwick offline | $O(n \log n)$ | $O(n)$ | không đệ quy, nhanh | đếm giá trị khác nhau, tổng/đếm có điều kiện |
| Gộp nhỏ vào lớn (set/map) | $O(n \log^2 n)$ | $O(n)$ | tổng quát nhất, giá trị tuỳ ý | màu lớn, thông tin phức tạp, đếm cặp |
| Sack (con nặng + cnt) | $O(n \log n)$ | $O(n)$ | nhanh, mảng thường | giá trị nhỏ ($\le n$) hoặc nén được |
Bảng 4. So sánh các cách trả lời câu hỏi “tập hợp” trên mọi cây con.
Khi đi thi: gặp “với mỗi đỉnh, hãy tính … trên cây con của nó” mà thông tin không cộng dồn được, em nghĩ ngay tới gộp nhỏ vào lớn: code ngắn, ít lỗi, $n = 2 \cdot 10^5$ chạy thoải mái. Chỉ chuyển sang sack khi giới hạn thời gian thật chặt, hoặc khi thao tác “xoá” dễ hơn “gộp hai cấu trúc”.
- 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)
- Dãy nghịch thế (NKINV) (Khá)
- Count Ways to Build Rooms in an Ant Colony (LeetCode 1916) (Khó)
- 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 Euler tour và gộp tập nhỏ vào lớn
Công ty có $n$ nhân viên tạo thành cây gốc 1 (giám đốc), nhân viên $i$ có lương $a_i$ ($n, q \le 2 \cdot 10^5$, $|a_i| \le 10^9$). Có $q$ thao tác: 1 u x: lương của $u$ tăng thêm $x$ ($|x| \le 10^9$); 2 u: in tổng lương của $u$ và mọi cấp dưới (trực tiếp hoặc gián tiếp) của $u$.
Input: dòng đầu $n, q$; dòng hai $a_1..a_n$; $n - 1$ dòng tiếp là các cạnh; $q$ dòng thao tác.
10 5
5 3 2 7 1 4 6 2 8 9
1 2
1 3
2 4
2 5
3 6
3 7
5 8
5 9
7 10
2 2
2 3
1 5 9
2 2
2 121
21
30
56📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
add(tin[u], x), không cần trừ giá trị cũ. Ở ví dụ, cây con của 2 gồm {2, 4, 5, 8, 9} có tổng 21; tăng lương nhân viên 5 thêm 9 thì tổng thành 30. Bản Python dựng Fenwick trong $O(n)$: cộng mỗi ô vào ô “cha” i + (i & −i) của nó.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200005;
int n, q, tin[MAXN], tout[MAXN];
long long bit[MAXN];
vector<int> adj[MAXN];
void add(int i, long long v){ for(; i <= n; i += i & -i) bit[i] += v; }
long long sum(int i){ long long s = 0; for(; i > 0; i -= i & -i) s += bit[i]; return s; }
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> q;
vector<long long> a(n + 1);
for(int i = 1; i <= n; i++) cin >> a[i];
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> par(n + 1, 0), it(n + 1, 0), st = {1};
int timer_ = 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(); }
}
for(int u = 1; u <= n; u++) add(tin[u], a[u]);
while(q--){
int t, u; cin >> t >> u;
if(t == 1){ long long x; cin >> x; add(tin[u], x); } // tăng a[u] thêm x
else cout << sum(tout[u]) - sum(tin[u] - 1) << "\n";
}
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n, q = int(data[0]), int(data[1])
a = [0] + [int(x) for x in data[2:2 + n]]
pos = 2 + n
adj = [[] for _ in range(n + 1)]
for _ in range(n - 1):
u, v = int(data[pos]), int(data[pos + 1]); pos += 2
adj[u].append(v); adj[v].append(u)
tin = [0] * (n + 1); tout = [0] * (n + 1); par = [0] * (n + 1); it = [0] * (n + 1)
timer = 1; tin[1] = 1; st = [1]
while st:
u = st[-1]
if it[u] < len(adj[u]):
v = adj[u][it[u]]; it[u] += 1
if v != par[u]:
par[v] = u; timer += 1; tin[v] = timer; st.append(v)
else:
tout[u] = timer; st.pop()
bit = [0] * (n + 1)
for u in range(1, n + 1):
bit[tin[u]] += a[u]
for i in range(1, n + 1): # dựng Fenwick trong O(n)
j = i + (i & -i)
if j <= n:
bit[j] += bit[i]
def pref(i):
s = 0
while i > 0:
s += bit[i]; i -= i & -i
return s
out = []
for _ in range(q):
t, u = int(data[pos]), int(data[pos + 1]); pos += 2
if t == 1:
x = int(data[pos]); pos += 1
i = tin[u]
while i <= n:
bit[i] += x; i += i & -i
else:
out.append(pref(tout[u]) - pref(tin[u] - 1))
print('\n'.join(map(str, out)))
main()Cây $n$ đỉnh gốc 1, đỉnh $i$ có giá trị ban đầu $a_i$ ($n, q \le 2 \cdot 10^5$). Thao tác 1 u x: cộng $x$ vào giá trị của mọi đỉnh trong cây con $u$; 2 u: in giá trị hiện tại của đỉnh $u$. ($|a_i|, |x| \le 10^9$.)
Input: như bài 1.
10 5
5 3 2 7 1 4 6 2 8 9
1 2
1 3
2 4
2 5
3 6
3 7
5 8
5 9
7 10
1 2 10
1 5 -3
2 8
2 4
2 39
17
2📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
add(tin[u], x), add(tout[u] + 1, −x); giá trị của $v$ = $a_v$ + sum(tin[v]). Ví dụ: đỉnh 8 nằm trong cây con 2 và cây con 5 nên nhận $10 - 3$, giá trị $2 + 7 = 9$; đỉnh 4 chỉ thuộc cây con 2: $7 + 10 = 17$.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200005;
int n, q, tin[MAXN], tout[MAXN];
long long bit[MAXN];
vector<int> adj[MAXN];
void add(int i, long long v){ for(; i <= n; i += i & -i) bit[i] += v; }
long long sum(int i){ long long s = 0; for(; i > 0; i -= i & -i) s += bit[i]; return s; }
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> q;
vector<long long> a(n + 1);
for(int i = 1; i <= n; i++) cin >> a[i];
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> par(n + 1, 0), it(n + 1, 0), st = {1};
int timer_ = 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 t, u; cin >> t >> u;
if(t == 1){
long long x; cin >> x;
add(tin[u], x); add(tout[u] + 1, -x); // cộng x cho cả đoạn [tin, tout]
} else cout << a[u] + sum(tin[u]) << "\n"; // giá trị = ban đầu + tổng mảng hiệu
}
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n, q = int(data[0]), int(data[1])
a = [0] + [int(x) for x in data[2:2 + n]]
pos = 2 + n
adj = [[] for _ in range(n + 1)]
for _ in range(n - 1):
u, v = int(data[pos]), int(data[pos + 1]); pos += 2
adj[u].append(v); adj[v].append(u)
tin = [0] * (n + 1); tout = [0] * (n + 1); par = [0] * (n + 1); it = [0] * (n + 1)
timer = 1; tin[1] = 1; st = [1]
while st:
u = st[-1]
if it[u] < len(adj[u]):
v = adj[u][it[u]]; it[u] += 1
if v != par[u]:
par[v] = u; timer += 1; tin[v] = timer; st.append(v)
else:
tout[u] = timer; st.pop()
bit = [0] * (n + 2)
def add(i, v):
while i <= n:
bit[i] += v; i += i & -i
out = []
for _ in range(q):
t, u = int(data[pos]), int(data[pos + 1]); pos += 2
if t == 1:
x = int(data[pos]); pos += 1
add(tin[u], x); add(tout[u] + 1, -x) # cộng x cho cả đoạn [tin, tout]
else:
i, s = tin[u], 0
while i > 0:
s += bit[i]; i -= i & -i
out.append(a[u] + s)
print('\n'.join(map(str, out)))
main()Cây $n$ đỉnh gốc 1, đỉnh $i$ có giá trị $a_i$ ($n, q \le 2 \cdot 10^5$, $|a_i|, |x| \le 10^9$). Thao tác 1 u x: tăng $a_u$ thêm $x$; 2 u: in tổng giá trị các đỉnh trên đường đi từ gốc 1 tới $u$ (tính cả hai đầu).
Input: như bài 1.
10 4
5 3 2 7 1 4 6 2 8 9
1 2
1 3
2 4
2 5
3 6
3 7
5 8
5 9
7 10
2 8
2 10
1 2 100
2 911
22
117📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
sum(tin[v]). Giá trị ban đầu cũng nạp bằng đúng thao tác này. Ví dụ đường 1 → 2 → 5 → 8 có tổng $5 + 3 + 1 + 2 = 11$.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200005;
int n, q, tin[MAXN], tout[MAXN];
long long bit[MAXN];
vector<int> adj[MAXN];
void add(int i, long long v){ for(; i <= n; i += i & -i) bit[i] += v; }
long long sum(int i){ long long s = 0; for(; i > 0; i -= i & -i) s += bit[i]; return s; }
void addVertex(int u, long long x){ add(tin[u], x); add(tout[u] + 1, -x); } // u ảnh hưởng cả cây con
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> q;
vector<long long> a(n + 1);
for(int i = 1; i <= n; i++) cin >> a[i];
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> par(n + 1, 0), it(n + 1, 0), st = {1};
int timer_ = 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(); }
}
for(int u = 1; u <= n; u++) addVertex(u, a[u]);
while(q--){
int t, u; cin >> t >> u;
if(t == 1){ long long x; cin >> x; addVertex(u, x); }
else cout << sum(tin[u]) << "\n"; // tổng các tổ tiên (kể cả u) của u
}
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n, q = int(data[0]), int(data[1])
a = [0] + [int(x) for x in data[2:2 + n]]
pos = 2 + n
adj = [[] for _ in range(n + 1)]
for _ in range(n - 1):
u, v = int(data[pos]), int(data[pos + 1]); pos += 2
adj[u].append(v); adj[v].append(u)
tin = [0] * (n + 1); tout = [0] * (n + 1); par = [0] * (n + 1); it = [0] * (n + 1)
timer = 1; tin[1] = 1; st = [1]
while st:
u = st[-1]
if it[u] < len(adj[u]):
v = adj[u][it[u]]; it[u] += 1
if v != par[u]:
par[v] = u; timer += 1; tin[v] = timer; st.append(v)
else:
tout[u] = timer; st.pop()
bit = [0] * (n + 2)
def add(i, v):
while i <= n:
bit[i] += v; i += i & -i
for u in range(1, n + 1): # u ảnh hưởng cả cây con của nó
add(tin[u], a[u]); add(tout[u] + 1, -a[u])
out = []
for _ in range(q):
t, u = int(data[pos]), int(data[pos + 1]); pos += 2
if t == 1:
x = int(data[pos]); pos += 1
add(tin[u], x); add(tout[u] + 1, -x)
else:
i, s = tin[u], 0
while i > 0:
s += bit[i]; i -= i & -i
out.append(s) # tổng các tổ tiên (kể cả u) của u
print('\n'.join(map(str, out)))
main()Cây $n$ đỉnh gốc 1 ($n \le 2 \cdot 10^5$), đỉnh $u$ có màu $c_u$ ($1 \le c_u \le 10^9$). Với mỗi đỉnh $u$, in số màu khác nhau trong cây con của $u$.
Input: dòng đầu $n$; dòng hai $c_1..c_n$; $n - 1$ dòng tiếp là các cạnh. Output: $n$ số trên một dòng.
10
1 2 1 3 2 3 1 2 1 3
1 2
1 3
2 4
2 5
3 6
3 7
5 8
5 9
7 103 3 2 1 2 1 2 1 1 1📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
set thì không quan tâm giá trị lớn hay nhỏ. Ví dụ: cây con 2 có màu {2, 3, 2, 2, 1} → 3 màu; cây con 3 có màu {1, 3, 1, 3} → 2 màu.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200005;
int n, c[MAXN], par[MAXN], ans[MAXN];
vector<int> adj[MAXN];
set<int> S[MAXN];
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n;
for(int i = 1; i <= n; i++) cin >> c[i];
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: cha đứng trước con
vector<bool> seen(n + 1, false); seen[1] = true;
for(int i = 0; i < (int)order.size(); i++)
for(int v : adj[order[i]]) if(!seen[v]){
seen[v] = true; par[v] = order[i]; order.push_back(v);
}
for(int u = 1; u <= n; u++) S[u].insert(c[u]);
for(int i = n - 1; i >= 0; i--){ // con được xử lý trước cha
int u = order[i];
ans[u] = S[u].size(); // mọi con của u đã gộp vào S[u]
int p = par[u];
if(p == 0) continue;
if(S[u].size() > S[p].size()) swap(S[u], S[p]); // O(1): chỉ đổi “ruột” hai set
for(int x : S[u]) S[p].insert(x); // đổ tập NHỎ vào tập LỚN
S[u].clear();
}
for(int u = 1; u <= n; u++) cout << ans[u] << " ";
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0])
c = [0] + [int(x) for x in data[1:1 + n]]
adj = [[] for _ in range(n + 1)]
pos = 1 + n
for _ in range(n - 1):
u, v = int(data[pos]), int(data[pos + 1]); pos += 2
adj[u].append(v); adj[v].append(u)
par = [0] * (n + 1); seen = [False] * (n + 1); seen[1] = True
order = [1] # BFS: cha đứng trước con
for u in order:
for v in adj[u]:
if not seen[v]:
seen[v] = True; par[v] = u; order.append(v)
S = [None] + [{c[u]} for u in range(1, n + 1)]
ans = [0] * (n + 1)
for u in reversed(order): # con được xử lý trước cha
ans[u] = len(S[u])
p = par[u]
if p == 0:
continue
small, big = S[u], S[p]
if len(small) > len(big):
small, big = big, small # chỉ đổi tham chiếu, O(1)
big.update(small) # đổ tập NHỎ vào tập LỚN
S[p] = big; S[u] = None
print(*ans[1:])
main()Cây $n$ đỉnh gốc 1 ($n \le 10^5$), đỉnh $u$ có màu $c_u$ ($1 \le c_u \le n$). Trong cây con của $u$, một màu gọi là chiếm ưu thế nếu không màu nào xuất hiện nhiều lần hơn nó (có thể có nhiều màu cùng chiếm ưu thế). Với mỗi $u$, in tổng các màu chiếm ưu thế trong cây con của $u$.
Input: như bài 4. Output: $n$ số trên một dòng.
5
1 2 3 2 3
1 2
1 3
2 4
3 55 2 3 2 3📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
distinct bằng hai biến mx (số lần xuất hiện lớn nhất) và sumMx (tổng các màu đạt mx). Khi thêm một đỉnh màu $c$: tăng cnt[c] thành $k$; nếu $k > mx$ thì mx = k, sumMx = c; nếu $k = mx$ thì sumMx += c. Không cần hỗ trợ xoá từng phần tử: khi keep = false ta xoá sạch, đặt lại cnt về 0 và mx = sumMx = 0. Ví dụ ở gốc: màu 2 và 3 đều xuất hiện 2 lần, tổng $2 + 3 = 5$. Tổng có thể vượt int.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
int n, c[MAXN], sz[MAXN], big[MAXN], tin[MAXN], tout[MAXN], ord_[MAXN], timer_ = 0, cnt[MAXN];
int mx = 0; // số lần xuất hiện lớn nhất hiện tại
long long sumMx = 0, ans[MAXN]; // tổng các màu đạt mx
vector<int> adj[MAXN];
void prep(int u, int p){
sz[u] = 1; tin[u] = ++timer_; ord_[timer_] = u;
for(int v : adj[u]) if(v != p){
prep(v, u); sz[u] += sz[v];
if(big[u] == 0 || sz[v] > sz[big[u]]) big[u] = v;
}
tout[u] = timer_;
}
void addV(int v){
int k = ++cnt[c[v]];
if(k > mx){ mx = k; sumMx = c[v]; }
else if(k == mx) sumMx += c[v];
}
void dfs(int u, int p, bool keep){
for(int v : adj[u]) if(v != p && v != big[u]) dfs(v, u, false);
if(big[u]) dfs(big[u], u, true);
addV(u);
for(int v : adj[u]) if(v != p && v != big[u])
for(int t = tin[v]; t <= tout[v]; t++) addV(ord_[t]);
ans[u] = sumMx;
if(!keep){ // xoá sạch: đặt lại cnt, mx, sumMx
for(int t = tin[u]; t <= tout[u]; t++) cnt[c[ord_[t]]] = 0;
mx = 0; sumMx = 0;
}
}
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n;
for(int i = 1; i <= n; i++) cin >> c[i];
for(int i = 1; i < n; i++){
int u, v; cin >> u >> v;
adj[u].push_back(v); adj[v].push_back(u);
}
prep(1, 0);
dfs(1, 0, true);
for(int u = 1; u <= n; u++) cout << ans[u] << " ";
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0])
c = [0] + [int(x) for x in data[1:1 + n]]
adj = [[] for _ in range(n + 1)]
pos = 1 + n
for _ in range(n - 1):
u, v = int(data[pos]), int(data[pos + 1]); pos += 2
adj[u].append(v); adj[v].append(u)
par = [0] * (n + 1); tin = [0] * (n + 1); tout = [0] * (n + 1); it = [0] * (n + 1)
order = [0, 1]; tin[1] = 1; st = [1]
while st:
u = st[-1]
if it[u] < len(adj[u]):
v = adj[u][it[u]]; it[u] += 1
if v != par[u]:
par[v] = u; tin[v] = len(order); order.append(v); st.append(v)
else:
tout[u] = len(order) - 1; st.pop()
sz = [1] * (n + 1); big = [0] * (n + 1)
for t in range(n, 1, -1):
v = order[t]; p = par[v]
sz[p] += sz[v]
if big[p] == 0 or sz[v] > sz[big[p]]:
big[p] = v
cpos = [c[v] for v in order]
cnt = [0] * (n + 1); ans = [0] * (n + 1)
mx = 0; smx = 0
stack = [(1, True, False)]
while stack:
u, keep, done = stack.pop()
if not done:
stack.append((u, keep, True))
if big[u]:
stack.append((big[u], True, False))
for v in adj[u]:
if v != par[u] and v != big[u]:
stack.append((v, False, False))
continue
cols = [c[u]]
for v in adj[u]:
if v != par[u] and v != big[u]:
cols += cpos[tin[v]:tout[v] + 1]
for col in cols:
cnt[col] += 1
k = cnt[col]
if k > mx:
mx = k; smx = col
elif k == mx:
smx += col
ans[u] = smx
if not keep:
for col in cpos[tin[u]:tout[u] + 1]:
cnt[col] = 0
mx = 0; smx = 0
print(*ans[1:])
main()Cây $n$ đỉnh gốc 1 ($n, q \le 2 \cdot 10^5$). Mỗi truy vấn cho $u, k$ ($0 \le k \le n$): đếm số đỉnh trong cây con của $u$ nằm thấp hơn $u$ đúng $k$ tầng (độ sâu bằng $\text{dep}[u] + k$).
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, k$.
10 5
1 2
1 3
2 4
2 5
3 6
3 7
5 8
5 9
7 10
1 2
2 2
3 1
1 0
5 34
2
2
1
0📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
tin tăng dần, tạo thành một danh sách byDep[d] (DFS thêm vào theo thứ tự vào nên tự tăng). Đỉnh nào trong danh sách có $\text{tin} \in [\text{tin}[u], \text{tout}[u]]$ thì thuộc cây con của $u$, đếm bằng hai lần tìm kiếm nhị phân. Mỗi truy vấn $O(\log n)$. Ví dụ: tầng 2 của cây gồm 4, 5, 6, 7, đều thuộc cây con gốc nên (1, 2) → 4; cây con 2 ở tầng 2 có 8, 9 nên (2, 2) → 2.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200005;
int n, q, tin[MAXN], tout[MAXN], dep[MAXN];
vector<int> adj[MAXN], byDep[MAXN]; // byDep[d]: tin của các đỉnh độ sâu d, tăng dần
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> par(n + 1, 0), it(n + 1, 0), st = {1};
int timer_ = 0; tin[1] = ++timer_; byDep[0].push_back(1);
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; dep[v] = dep[u] + 1; tin[v] = ++timer_;
byDep[dep[v]].push_back(tin[v]); // thêm theo thứ tự vào nên tự tăng dần
st.push_back(v);
} else { tout[u] = timer_; st.pop_back(); }
}
while(q--){
int u, k; cin >> u >> k;
int d = dep[u] + k;
if(d >= n){ cout << 0 << "\n"; continue; }
vector<int> &w = byDep[d];
cout << upper_bound(w.begin(), w.end(), tout[u]) - lower_bound(w.begin(), w.end(), tin[u]) << "\n";
}
return 0;
}import sys
from bisect import bisect_left, bisect_right
def main():
data = sys.stdin.buffer.read().split()
n, q = int(data[0]), int(data[1])
adj = [[] for _ in range(n + 1)]
pos = 2
for _ in range(n - 1):
u, v = int(data[pos]), int(data[pos + 1]); pos += 2
adj[u].append(v); adj[v].append(u)
tin = [0] * (n + 1); tout = [0] * (n + 1); par = [0] * (n + 1); it = [0] * (n + 1); dep = [0] * (n + 1)
by_dep = [[] for _ in range(n)]
timer = 1; tin[1] = 1; by_dep[0].append(1); st = [1]
while st:
u = st[-1]
if it[u] < len(adj[u]):
v = adj[u][it[u]]; it[u] += 1
if v != par[u]:
par[v] = u; dep[v] = dep[u] + 1; timer += 1; tin[v] = timer
by_dep[dep[v]].append(timer) # tự tăng dần
st.append(v)
else:
tout[u] = timer; st.pop()
out = []
for _ in range(q):
u, k = int(data[pos]), int(data[pos + 1]); pos += 2
d = dep[u] + k
if d >= n:
out.append(0); continue
w = by_dep[d]
out.append(bisect_right(w, tout[u]) - bisect_left(w, tin[u]))
print('\n'.join(map(str, out)))
main()Công ty $n$ nhân viên dạng cây gốc 1 ($n \le 2 \cdot 10^5$), lương $a_i$ ($1 \le a_i \le 10^9$). Với mỗi nhân viên $u$, đếm số cấp dưới $v$ (trực tiếp hoặc gián tiếp, $v \ne u$) có lương nhỏ hơn hẳn $a_u$.
Input: dòng đầu $n$; dòng hai $a_1..a_n$; $n - 1$ dòng tiếp là các cạnh. Output: $n$ số trên một dòng.
10
5 3 2 7 1 4 6 2 8 9
1 2
1 3
2 4
2 5
3 6
3 7
5 8
5 9
7 105 2 0 0 0 0 0 0 0 0📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
tin[v] trên Fenwick. Khi tới lượt $u$, các ô đã bật chính là các đỉnh lương nhỏ hơn, nên đáp án = số ô đã bật trong đoạn $[\text{tin}[u], \text{tout}[u]]$. Cẩn thận với lương bằng nhau: xử lý theo nhóm, hỏi hết cả nhóm rồi mới bật cả nhóm. Ví dụ: cây con 2 có lương {3, 7, 1, 2, 8}, trong đó 1 và 2 nhỏ hơn 3 nên đáp án của 2 là 2 (đỉnh 8 lương 2 là cấp dưới gián tiếp qua 5, vẫn được tính). Gốc có lương 5, các cấp dưới lương 3, 2, 1, 4, 2 nhỏ hơn nên đáp án là 5.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200005;
int n, tin[MAXN], tout[MAXN], bit[MAXN];
long long a[MAXN];
vector<int> adj[MAXN];
void add(int i){ for(; i <= n; i += i & -i) bit[i]++; }
int sum(int i){ int s = 0; for(; i > 0; i -= i & -i) s += bit[i]; return s; }
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
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> par(n + 1, 0), it(n + 1, 0), st = {1};
int timer_ = 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(); }
}
vector<int> id(n);
iota(id.begin(), id.end(), 1);
sort(id.begin(), id.end(), [](int x, int y){ return a[x] < a[y]; });
vector<int> ans(n + 1);
for(int i = 0; i < n; ){
int j = i;
while(j < n && a[id[j]] == a[id[i]]) j++; // nhóm giá trị bằng nhau
for(int k = i; k < j; k++){ // hỏi trước: chỉ đếm số NHỎ HƠN
int u = id[k];
ans[u] = sum(tout[u]) - sum(tin[u] - 1);
}
for(int k = i; k < j; k++) add(tin[id[k]]); // rồi mới bật cả nhóm
i = j;
}
for(int u = 1; u <= n; u++) cout << ans[u] << " ";
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0])
a = [0] + [int(x) for x in data[1:1 + n]]
adj = [[] for _ in range(n + 1)]
pos = 1 + n
for _ in range(n - 1):
u, v = int(data[pos]), int(data[pos + 1]); pos += 2
adj[u].append(v); adj[v].append(u)
tin = [0] * (n + 1); tout = [0] * (n + 1); par = [0] * (n + 1); it = [0] * (n + 1)
timer = 1; tin[1] = 1; st = [1]
while st:
u = st[-1]
if it[u] < len(adj[u]):
v = adj[u][it[u]]; it[u] += 1
if v != par[u]:
par[v] = u; timer += 1; tin[v] = timer; st.append(v)
else:
tout[u] = timer; st.pop()
bit = [0] * (n + 1)
def pref(i):
s = 0
while i > 0:
s += bit[i]; i -= i & -i
return s
ids = sorted(range(1, n + 1), key=lambda x: a[x])
ans = [0] * (n + 1)
i = 0
while i < n:
j = i
while j < n and a[ids[j]] == a[ids[i]]:
j += 1
for k in range(i, j): # hỏi trước: chỉ đếm số NHỎ HƠN
u = ids[k]
ans[u] = pref(tout[u]) - pref(tin[u] - 1)
for k in range(i, j): # rồi mới bật cả nhóm
x = tin[ids[k]]
while x <= n:
bit[x] += 1; x += x & -x
i = j
print(*ans[1:])
main()Cho cây $n$ đỉnh ($n \le 2 \cdot 10^5$) và số nguyên $K$ ($1 \le K \le n$). Đếm số cặp đỉnh không thứ tự $\{x, y\}$ mà đường đi giữa chúng có đúng $K$ cạnh.
Input: dòng đầu $n, K$; $n - 1$ dòng tiếp là các cạnh.
10 3
1 2
1 3
2 4
2 5
3 6
3 7
5 8
5 9
7 1010📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
map<độ sâu, số đỉnh>. Mỗi cặp $\{x, y\}$ được đếm đúng một lần tại $p = \text{LCA}(x, y)$, lúc hai phía chứa $x$ và $y$ được gộp lại. Khoảng cách $= \text{dep}[x] + \text{dep}[y] - 2\,\text{dep}[p]$, nên với mỗi độ sâu $d$ trong tập nhỏ, số đỉnh ghép được là số đỉnh có độ sâu $2\,\text{dep}[p] + K - d$ trong tập lớn. Đếm hết cặp trước rồi mới chèn tập nhỏ vào. Lưu độ sâu tuyệt đối (tính từ gốc) để không phải sửa lại khoá khi đi lên. Đáp án tới cỡ $n^2 / 2$: dùng long long. Ví dụ có 10 cặp cách nhau 3 cạnh, chẳng hạn (4, 3), (8, 1), (10, 1), (8, 4).Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200005;
int n, K, par[MAXN], dep[MAXN];
vector<int> adj[MAXN];
map<int, int> M[MAXN]; // M[u][d] = số đỉnh ở độ sâu d (tính từ gốc) trong cây con u
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> K;
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;
for(int i = 0; i < (int)order.size(); i++)
for(int v : adj[order[i]]) if(!seen[v]){
seen[v] = true; par[v] = order[i]; dep[v] = dep[order[i]] + 1; order.push_back(v);
}
for(int u = 1; u <= n; u++) M[u][dep[u]] = 1;
long long ans = 0;
for(int i = n - 1; i > 0; i--){
int u = order[i], p = par[u];
if(M[u].size() > M[p].size()) swap(M[u], M[p]); // M[u] giờ là tập nhỏ
for(auto [d, c] : M[u]){ // đếm cặp có LCA = p trước khi gộp
auto f = M[p].find(2 * dep[p] + K - d);
if(f != M[p].end()) ans += 1LL * c * f->second;
}
for(auto [d, c] : M[u]) M[p][d] += c;
M[u].clear();
}
cout << ans;
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n, K = int(data[0]), int(data[1])
adj = [[] for _ in range(n + 1)]
pos = 2
for _ in range(n - 1):
u, v = int(data[pos]), int(data[pos + 1]); pos += 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]
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)
M = [None] + [{dep[u]: 1} for u in range(1, n + 1)]
ans = 0
for u in reversed(order[1:]):
p = par[u]
small, big = M[u], M[p]
if len(small) > len(big):
small, big = big, small
target = 2 * dep[p] + K
for d, c in small.items(): # đếm cặp có LCA = p trước khi gộp
ans += c * big.get(target - d, 0)
for d, c in small.items():
big[d] = big.get(d, 0) + c
M[p] = big; M[u] = None
print(ans)
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