Lời giải Problem of the Week 1
bedao
đã đăng vào 9, Tháng 9, 2023, 13:00
Cách 1: Mo's algorithm
Bài này các bạn có thể giải trong ~\mathcal{O}((N+Q)\sqrt{N})~ sử dụng Mo algorithm và Euler tour on tree.
Coi mô hình công ty là một đồ thị dạng cây và ngôn ngữ lập trình yêu thích của một người ứng với màu của đỉnh đó. Với mỗi truy vấn đỉnh ~u~, ta cần tìm số màu xuất hiện ít nhất ~1~ lần và nhỏ hơn ~k~ lần trong cây con gốc ~u~ ~(*)~.
Gọi ~tin[u]~ là thời điểm đầu tiên duyệt đỉnh ~u~ và ~tout[u]~ là thời điểm duyệt xong toàn bộ cây con gốc ~u~ khi duyệt các đỉnh trên cây theo đường đi Euler. Sử dụng tính chất ~v~ là đỉnh thuộc cây con gốc ~u~ khi ~tin[u] \le tin[v] \le tout[u]~ (chứng minh ở đây), với mỗi truy vấn, ta cần tìm số màu thỏa mãn ~(*)~ trong đoạn từ ~tin[u]~ đến ~tout[u]~.
Đây là một bài toán cơ bản áp dụng Mo algorithm. Ta gọi ~ans~ là số màu thỏa mãn ~(*)~ hiện tại. Khi thêm một màu ~x~ vào, nếu số lần xuất hiện của màu đó sau khi được tăng lên từ ~0~ thành ~1~, ta cộng ~ans~ thêm ~1~, bởi lúc này màu ~x~ sẽ thỏa mãn điều kiện ~(*)~ ~(1 \le cnt[x] \le k)~. Nếu số lần xuất hiện tăng từ ~k~ lên ~k+1~, ta trừ ~ans~ đi ~1~ (màu này trước đấy thỏa mãn ~(*)~ nhưng giờ không còn thỏa mãn điều kiện đó nữa). Tương tự khi xóa một màu, nếu số lần xuất hiện trở về ~0~, ta trừ ~ans~ đi ~1~, còn nếu số lần xuất hiện trở về ~k~, ta cộng ~ans~ thêm ~1~. Các bạn có thể tham khảo code sau để hiểu rõ hơn.
Code tham khảo:
/* Tag: Mo, Euler tour */ #include <bits/stdc++.h> #define ii pair<int, int> #define st first #define nd second #define endl "\n" #define all(v) v.begin(), v.end() #define Unique(v) v.erase(unique(all(v)), v.end()) using namespace std; const int maxn = 1e5 + 5; int n, m, k, q; vector<int> g[maxn]; int c[maxn]; int tin[maxn], tout[maxn], Time = 0, ver[maxn]; void dfs (int u, int P){ tin[u] = ++Time; ver[Time] = u; for (auto v : g[u]){ if (v == P) continue; dfs(v, u); } tout[u] = Time; } const int S = 350; struct Query{ int id, l, r; Query(int _id = 0, int _l = 0, int _r = 0): id(_id), l(_l), r(_r) {} bool operator < (const Query &other) const{ return (l / S < other.l / S) || (l / S == other.l / S && r < other.r); } }; int res[maxn]; int cnt[maxn], ans = 0; vector<Query> qu; void add(int col){ cnt[col]++; if (cnt[col] == 1) ans++; if (cnt[col] == k + 1) ans--; } void sub(int col){ cnt[col]--; if (cnt[col] == 0) ans--; if (cnt[col] == k) ans++; } void PROGRAM(int _){ cin >> n >> m >> k; for (int u = 2; u <= n; u++){ int par; cin >> par; g[par].push_back(u); } dfs(1, 0); for (int u = 1; u <= n; u++) cin >> c[u]; cin >> q; for (int i = 1; i <= q; i++){ int u; cin >> u; qu.push_back(Query(i, tin[u], tout[u])); } int pl = 1, pr = 0; sort(qu.begin(), qu.end()); for (int i = 0; i < q; i++){ int id = qu[i].id, l = qu[i].l, r = qu[i].r; while (pl > l){ pl--; add(c[ver[pl]]); } while (pr < r){ pr++; add(c[ver[pr]]); } while (pl < l){ sub(c[ver[pl]]); pl++; } while (pr > r){ sub(c[ver[pr]]); pr--; } res[id] = ans; } for (int i = 1; i <= q; i++){ cout << res[i] << endl; } } signed main(){ ios_base::sync_with_stdio(false); cin.tie(0); int test = 1; for (int _ = 1; _ <= test; _++){ PROGRAM(_); } return 0; }
Cách 2: Small to large
Bài này chúng ta có thể giải bằng kĩ thuật Small To Large.
Ta có thể mô hình hóa công ty này ở dạng cây với đỉnh gốc là ~1~. Bài toán bây giờ chuyển đổi thành, với mỗi truy vấn, xác định xem có bao nhiêu màu có số lần xuất hiện trong đoạn ~[1,k]~ trong cây con gốc ~u~.
Ta gọi ~S(u)~ là tập các cặp giá trị ~(x,y)~, mang ý nghĩa màu ~x~ xuất hiện ~y~ lần ~(y > 0)~ trong cây con gốc ~u~ hiện tại ta đang xét. Ở đây, ta định nghĩa ~S(u)(x) = y~. Đồng thời gọi ~res(u)~ là đáp án nếu truy vấn đỉnh ~u~.
Đối với quá trình gộp tập màu của cây con hiện tại của đỉnh ~u~ với tập màu của cây con của đỉnh ~v~ (~v~ là con trực tiếp của ~u~), hay thực chất là hợp tập ~S(v)~ vào với ~S(u)~, ta làm như sau:
- Kí hiệu ~|S(u)|~ là độ lớn của tập ~S(u)~. Nếu ~|S(v)| > |S(u)|~, ta đảo giá trị hai tập này cho nhau và gán ~res(u) = res(v)~, tức là giờ thay vì hợp tập ~v~ vào tập ~u~, ta đi hợp tập ~u~ vào tập ~v~. Điều này vẫn cho ra kết quả tập mới không đổi, nhưng do ta chỉ duyệt tập có độ lớn bé hơn, nên ta sẽ thu được độ phức tạp tốt hơn. Chứng minh chi tiết các bạn có thể đọc ở phần link hướng dẫn bên trên.
- Giờ ta duyệt qua từng phần tử ~(x,y)~ trong ~S(v)~:
- Gọi ~val = S(u)(x)~, giờ ta có hai trường hợp:
- Nếu ~val = 0~ và ~y <= k~, tức là màu ~x~ chưa xuất hiện ở trong tập ~S(u)~, và do khi gộp hai tập lại, màu này sẽ xuất hiện không quá ~k~ lần nên ta cần tăng ~res(u)~ lên ~1~ đơn vị.
- Nếu ~0 < val \le k~ và ~val + y > k~, tức là trước đó màu ~x~ đã xuất hiện rồi và số lần xuất hiện của nó thì nằm trong khoảng ~[1,k]~, vậy nên khi gộp hai tập vào và ta làm số lần xuất hiện của nó vượt quá ~k~, ta cần giảm ~res(u)~ đi một đơn vị.
- Sau đó, nếu chưa tồn tại màu ~x~ trong tập ~S(u)~ (trường hợp ~val=0~) thì ta thêm phần tử ~(x,y)~ vào ~S(u)~, ngược lại ta xóa phần tử ~(x,val)~ ra và thay bằng phần tử ~(x,y+val)~.
- Gọi ~val = S(u)(x)~, giờ ta có hai trường hợp:
- Dễ thấy, ta có thể biểu diễn tập ~S~ và các phép đảo giá trị tập, thêm, xóa phần tử bằng cấu trúc dữ liệu
std::map. Lưu ý rằng việc đảo giá trị tập bằngstd::mapchỉ mất ~O(1)~.
Độ phức tạp: ~O(N \times {\log_{N}}^2)~
Code tham khảo:
#include<bits/stdc++.h> using namespace std; const int N = 1e5+5; int n,m,k,q; vector<int> adj[N]; map<int,int> mp[N]; int res[N]; int c[N]; void dfs (int u, int p) { mp[u][c[u]]++; res[u] = 1; for (auto v : adj[u]) { if (v == p) continue; dfs(v,u); if (mp[u].size() < mp[v].size()) { swap(mp[u],mp[v]); res[u] = res[v]; } for (auto it : mp[v]) { int x = mp[u][it.first]; if (x == 0) { if (x + it.second <= k) res[u]++; } else { if (x <= k && x + it.second > k) res[u]--; } mp[u][it.first] += it.second; } } } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cin >> n >> m >> k; for (int i=2; i<=n; i++) { int u; cin >> u; adj[u].push_back(i); } for (int i=1; i<=n; i++) cin >> c[i]; dfs(1,0); cin >> q; while (q--) { int u; cin >> u; cout << res[u] << '\n'; } }
Cách 3: DSU on Tree
Tổng quan
Một cách tóm tắt, bài này ta có thể sử dụng kỹ thuật DSU on tree (Sack) với mảng đếm phân phối.
Ta sử dụng data structure ~CountingTable~ là một mảng đếm phân phối có thể thực hiện những thao tác sau:
| Thao tác | Độ phức tạp |
|---|---|
| Tạo mới | ~O(m)~ |
| Xóa một phần tử ~x~ | ~O(1)~ |
| Thêm một phần tử ~x~ | ~O(1)~ |
Đếm số lượng giá trị ~x~ xuất hiện trong ~CountingTable~ ít nhất một lần và không quá ~k~ lần |
~O(1)~ |
Thuật toán
Các bước mô hình hóa bài toán thành dạng cây với mỗi nút ~u~ mang một màu sắc ~col[u]~ được lược bỏ.
Ta sẽ giải bài toán trên toàn bộ các nút của cây và lưu kết quả của nút ~u~ vào ~res[u]~. Với mỗi truy vấn nút ~v~ thì ta chỉ cần xuất ra ~res[v]~ trong ~O(1)~.
Trong bài tập này, ta gọi tắt ~CountingTable~ là ~DS~.
Sau đây là các ý tưởng xử lý bài toán trên toàn bộ các nút của cây:
Thuật toán trâu
Với mỗi đỉnh ~u~ (xét theo thứ tự post-order DFS), ta có thể tạo một ~DS[u]~ mới cho nút đó. Với mỗi giá trị đã được thêm vào ~DS[v]~ (với ~v~ là nút con trực tiếp của ~u~) và giá trị ~col[u]~, ta sẽ lần lượt thêm giá trị này vào ~DS[u]~. Sau đó cập nhật kết quả ~res[u]~.
Đánh giá
Thuật toán này đảm bảo về tính đúng đắn nhưng xét về độ phức tạp thời gian thì sẽ tốn đến ~O(nm+n^2)~ (Tốn ~O(nm)~ để tạo mới toàn bộ các ~DS~ cho toàn bộ nút và tốn ~O(n^2)~ cho toàn bộ các thao tác cập nhật thêm vào ~DS~).
Thuật toán cải tiến
Ta vẫn tiếp tục xét lần lượt các đỉnh ~u~ theo post-order DFS tuy nhiên ta sẽ xét 2 trường hợp:
- Đỉnh đang xét là nút lá: Tạo mới ~DS[u]~ và thêm ~col[u]~ vào ~DS[u]~. Sau đó cập nhật kết quả ~res[u]~.
- Đỉnh đang xét khác nút lá:
- Tìm nút ~C_u~ là nút có cây con gốc ~C_u~ lớn nhất trong tất cả cây con gốc ~v~ (với ~v~ là con trực tiếp của ~u~).
- Thay vì tạo mới ~DS[u]~, ta sẽ thừa hưởng lại thông tin từ ~DS[C_u]~ (trong ~O(1)~). Nghĩa là ~DS[u]\colon=DS[C_u]~.
- Với mỗi đỉnh ~v~ là nút con trực tiếp của ~u~ và khác ~C_u~, ta thêm toàn bộ giá trị đã được thêm vào ~DS[v]~ vào ~DS[u]~. Sau đó cập nhật kết quả ~res[u]~.
Đánh giá thuật toán
Ta sẽ đánh dấu các cạnh nối từ ~u~ đến ~C_u~ là cạnh nặng và toàn bộ các cạnh còn lại là cạnh nhẹ. Dễ dàng nhìn thấy số lượng lần giá trị ~col[v]~ với ~v~ là một nút bất kỳ được thêm vào ~DS[u]~ với ~u~ là một đỉnh bất kỳ đúng bằng số lượng cạnh nhẹ nằm trên đường đi đơn từ ~u~ đến ~1~.
Cách đánh dấu cạnh nặng và cạnh nhẹ này tương tự như cách đánh dấu cạnh của kỹ thuật ~HLD~ (Heavy-Light Decomposition). Kỹ thuật này chứng minh được rằng số lượng cạnh nhẹ trên đường đi đơn từ một đỉnh bất kỳ đến nút gốc là không vượt quá ~O(\log(n))~.
Gọi ~k~ là số lượng nút là của cây thì số lần tạo mới ~DS[u]~ cũng là ~k~ lần và tốn độ phức tạp thời gian là ~O(mk)~.
Từ các chứng minh về số lượng cạnh nhẹ, ta dễ dàng thấy rằng tổng độ phức tạp thời gian của các thao tác cập nhật thêm vào các ~DS~ là ~O(n\log(n))~.
Vì thế tổng độ phức tạp thời gian là ~O(n\log(n) + mk)~. Trong trường hợp tệ nhất thì có thể sẽ lên đến ~O(mn)~.
Thuật toán ~O(n\log(n) + m)~
Dựa vào độ phức tạp của thuật toán thì có thể đoán ra được ta sẽ chỉ tạo duy nhất 1 ~DS~ cho toàn bộ tất cả các nút.
Một nhận xét quan trọng đó là với thuật toán cải tiến ở trên thì với nút ~u~ không phải nút lá thì khi ~DS[u]~ thừa hưởng thông tin từ ~DS[C_u]~, ta không cần đến các ~DS[v]~ khác.
Từ nhận xét trên ta có thể đưa ra thuật toán:
Xét lần lượt các đỉnh ~u~ theo post-order DFS, xét 2 trường hợp:
- Đỉnh đang xét là nút lá: Thêm ~col[u]~ vào ~DS~. Sau đó cập nhật kết quả ~res[u]~.
- Đỉnh đang xét khác nút lá:
- Tìm nút ~C_u~ là nút có cây con gốc ~C_u~ lớn nhất trong tất cả cây con gốc ~v~ (với ~v~ là con trực tiếp của ~u~).
- Thứ tự được duyệt của các nút con trực tiếp của ~u~ trong
DFSđảm bảo nút ~C_u~ là nút cuối cùng và được xử lý đặc biệt. - Ngay sau khi xét và cập nhật kết quả đỉnh ~v~ với ~v~ là con trực tiếp của ~u~ và khác ~C_u~, ta loại bỏ tất các các giá trị ~col[z]~ với ~z~ là đỉnh thuộc cây con gốc ~v~ ra khỏi ~DS~.
- Sau khi xét và cập nhật kết quả đỉnh ~C_u~, ta không xóa các giá trị ra khỏi ~DS~.
- Thêm ~col[u]~ vào ~DS~.
- Thêm ~col[z]~ vào ~DS~ với ~z~ là nút thuộc cây con gốc ~v~ với ~v~ là nút con trực tiếp của ~u~ và khác ~C_u~.
- Cập nhật kết quả ~res[u]~.
Đánh giá thuật toán
Có thể thấy ta chỉ sử dụng đúng 1 ~DS~ vì thế sẽ không tốn chi phí tạo mới ~DS~.
Về tính đúng đắn của thuật toán, việc loại bỏ toàn bộ giá trị ~col[z]~ ra khỏi ~DS~ ngay sau khi tính xong ~res[v]~ tương đương với việc xóa ~DS[v]~ và khi xét tới đỉnh ~v'~ mới sẽ đảm bảo ~DS~ rỗng.
Việc xét và tính ~res[C_u]~ cuối cùng mà không làm rỗng ~DS~ tương đương với việc ~DS[u]~ thừa hưởng ~DS[C_u]~.
Về mặt bản chất, thuật toán này tương tự thuật toán cải tiến phía trên.
Đánh giá về độ phức tạp: ~O(n\log(n) + m)~.
Mẹo cài đặt
Để có thể duyệt qua nhanh tất cả các nút thuộc cây con gốc ~u~, ta có thể sử dụng kỹ thuật Euler tour để thuận tiện cho cài đặt và tăng nhẹ hiệu suất chạy chương trình.
Cài đặt
#include <bits/stdc++.h> using namespace std; const int N = 1e5+7; int n, m, k; vector<int> adj[N]; int euler[N], sta[N], fin[N], sz[N]; int col[N]; int res[N]; struct CountingTable { int cnt[N]; int ans; bool isValid(int d) { return (0 < d) && (d <= k); } void update(int x, int delta) { ans -= isValid(cnt[x]); cnt[x] += delta; ans += isValid(cnt[x]); } void add(int x) { update(x, 1); } void del(int x) { update(x, -1); } } DS; void euler_tour(int u) { static int cnt = 0; euler[++cnt] = u; sta[u] = cnt; for(int v: adj[u]) euler_tour(v); fin[u] = cnt; sz[u] = fin[u] - sta[u] + 1; } void cal_ans(int u) { int C = 0; for(int v: adj[u]) if(sz[v] > sz[C]) C = v; for(int v: adj[u]) if(v != C) { cal_ans(v); for(int z = sta[v]; z <= fin[v]; z++) { int u = euler[z]; DS.del(col[u]); } } if(C != 0) cal_ans(C); DS.add(col[u]); for(int v: adj[u]) if(v != C) { for(int z = sta[v]; z <= fin[v]; z++) { int u = euler[z]; DS.add(col[u]); } } res[u] = DS.ans; } int main() { cin>>n>>m>>k; for(int i = 2; i <= n; i++) { int p; cin >> p; adj[p].push_back(i); } for(int i = 1; i <= n; i++) cin >> col[i]; euler_tour(1); cal_ans(1); int q; cin >> q; while(q--) { int u; cin >> u; cout << res[u] << "\n"; } return 0; }
