Small to Large Merging

Cây $n \le 10^5$ đỉnh gốc $1$ , mỗi đỉnh có một màu. Với mỗi đỉnh $v$ , tìm tổng các màu xuất hiện nhiều lần nhất trong cây con của $v$ , trong $O(n \log^2 n)$ .

Đếm lại từ đầu cho từng cây con tốn $O(n^2)$ trên một cây hình đường thẳng. Thay vào đó, mỗi đỉnh giữ một bảng đếm màu của cây con mình, dựng bằng cách gộp bảng của các con. Mẹo nằm ở chiều gộp: luôn đổ bảng nhỏ vào bảng lớn. Mỗi lần một màu bị chuyển sang bảng khác, bảng mới chứa nó lớn ít nhất gấp đôi bảng cũ, nên một màu chỉ bị chuyển nhiều nhất $\log_2 n$ lần. Cùng ý tưởng đó, nếu giữ lại kết quả của con có cây con lớn nhất và chỉ làm lại phần còn lại, ta được một cách cài nhanh hơn chỉ dùng mảng đếm, rất hợp với các bài thống kê trên mọi cây con.

IĐổ tập nhỏ vào tập lớn

Bài toán ở đầu bài: mỗi đỉnh có màu $c_v \le n$ ; với mỗi $v$ , gọi các màu có số lần xuất hiện lớn nhất trong cây con của $v$ là màu chiếm ưu thế, và tính tổng của chúng.

Mỗi đỉnh $u$ giữ một bảng cnt[u] (một map từ màu tới số lần xuất hiện) của cây con $u$ , cùng hai số: tần suất lớn nhất $mx_u$ và tổng các màu đạt tần suất đó $sm_u$ . Thêm $k$ lần màu $c$ vào bảng thì số lần của $c$ tăng lên $f$ ; nếu $f > mx_u$ thì $c$ là màu chiếm ưu thế duy nhất, còn nếu $f = mx_u$ thì cộng thêm $c$ vào tổng. Số lần xuất hiện chỉ tăng nên không bao giờ phải tìm lại tần suất lớn nhất từ đầu.

Để dựng bảng của $u$ sau khi đã có bảng của mọi con:

Chọn con $b$ có bảng lớn nhất, lấy luôn bảng đó làm bảng của $u$ . Trong C++, swap(cnt[u], cnt[b]) đổi hai map trong $O(1)$ , không chép từng phần tử.
Thêm màu của chính $u$ .
Đổ từng phần tử của bảng các con còn lại vào bảng của $u$ , rồi xóa bảng đó.

Chứng minh

Xét một lần xuất hiện của màu ở đỉnh $x$ . Mỗi lần nó bị chuyển sang bảng khác, nó đang nằm trong một bảng không phải lớn nhất, và được đổ vào bảng của con lớn nhất cùng cha; sau khi gộp, bảng chứa nó có kích thước ít nhất gấp đôi bảng cũ. Kích thước bảng không vượt $n$ , nên nó bị chuyển nhiều nhất $\log_2 n$ lần. Có $n$ lần xuất hiện, nên tổng số lần chuyển là $O(n \log n)$ , mỗi lần tốn $O(\log n)$ cho map.

Ở đây kích thước bảng là số màu khác nhau, chưa hẳn là số đỉnh của cây con, nhưng lập luận trên vẫn đúng: một màu bị đổ vào bảng lớn hơn thì số màu của bảng mới ít nhất gấp đôi số màu của bảng chứa nó trước đó.

Ví dụTổng Các Màu Chiếm Ưu Thế

Đề. Cây $n \le 10^5$ đỉnh gốc $1$ , đỉnh $i$ có màu $c_i \le n$ . Với mỗi đỉnh, in tổng các màu chiếm ưu thế trong cây con của nó.

Lời giải. Làm đúng ba bước trên trong một lượt DFS, xử lý các con trước rồi mới tới $u$ . Khi đổ bảng của con $v$ vào, mỗi cặp (màu, số lần) được thêm một lần với cả số lần đó. Sau khi gộp xong thì xóa bảng của $v$ để giải phóng bộ nhớ. Tổng các màu có thể tới $n \cdot n = 10^{10}$ , nên dùng long long.

Code đầy đủ

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll N = 1e5 + 5;
ll n, c[N], mx[N], sm[N], ans[N];
vector<ll> g[N];
map<ll, ll> cnt[N];

void add(ll u, ll col, ll k) {
    ll f = (cnt[u][col] += k);
    if (f > mx[u]) mx[u] = f, sm[u] = col;
    else if (f == mx[u]) sm[u] += col;
}

void dfs(ll u, ll p) {
    ll big = 0;
    for (ll v : g[u])
        if (v != p) {
            dfs(v, u);
            if (!big || cnt[v].size() > cnt[big].size()) big = v;
        }
    if (big) {
        swap(cnt[u], cnt[big]);
        mx[u] = mx[big];
        sm[u] = sm[big];
    }
    add(u, c[u], 1);
    for (ll v : g[u])
        if (v != p && v != big) {
            for (pair<ll, ll> e : cnt[v]) add(u, e.first, e.second);
            cnt[v].clear();
        }
    ans[u] = sm[u];
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (ll i = 1; i <= n; i++) cin >> c[i];
    for (ll i = 1; i < n; i++) {
        ll a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    dfs(1, 0);
    for (ll i = 1; i <= n; i++) cout << ans[i] << (i == n ? '\n' : ' ');
}

Input7
1 2 2 3 3 3 2
1 2
1 3
2 4
2 5
3 6
3 7

Output5 3 2 3 3 3 2

Độ phức tạp: $O(n \log^2 n)$ , với $n = 10^5$ cần khoảng $3 \cdot 10^7$ phép tính.

Hỏi nhanh

Ở bước 1, một bạn chép bảng của con lớn nhất bằng phép gán cnt[u] = cnt[big] thay cho swap. Trên một cây hình đường thẳng $n = 10^5$ đỉnh, mỗi đỉnh một màu khác nhau, chương trình chạy ra sao?

IIGiữ lại con nặng

Cách trên cần mỗi đỉnh một map. Khi giá trị nhỏ (màu tới $n$ , độ sâu tới $n$ ), có một cách chỉ dùng một mảng đếm toàn cục và nhanh hơn một bậc $\log$ , thường được gọi là sack (hay DSU on tree).

Gọi con nặng của $u$ là con có cây con lớn nhất (nhiều đỉnh nhất), các con còn lại là con nhẹ. Ta duyệt cây theo thứ tự Euler (bài 3.2.1) để cây con của $u$ là đoạn liền $[tin_u, tout_u]$ trong mảng $ord$ , với $ord_t$ là đỉnh có $tin$ bằng $t$ . Hàm dfs2(u, keep) để lại trong mảng đếm đúng các đỉnh của cây con $u$ nếu keep đúng, và để lại mảng rỗng nếu keep sai:

Gọi dfs2(v, false) cho mọi con nhẹ $v$ : tính xong đáp án của chúng rồi xóa sạch mảng đếm.
Gọi dfs2(h, true) cho con nặng $h$ : mảng đếm giữ nguyên cây con của $h$ .
Thêm lại mọi đỉnh của các con nhẹ (duyệt đoạn Euler của chúng) và thêm chính $u$ . Lúc này mảng đếm chứa đúng cây con của $u$ ; trả lời các câu hỏi gắn với $u$ .
Nếu keep sai thì xóa mọi đỉnh của cây con $u$ khỏi mảng đếm.

Cạnh cam nối mỗi đỉnh với con nặng, con có cây con lớn nhất; số nhỏ dưới đỉnh là kích thước cây con.

Chứng minh

Một đỉnh $x$ chỉ bị thêm hay xóa thêm lần nữa ở bước 3, 4 khi một tổ tiên của nó được xử lý mà $x$ nằm trong cây con của một con nhẹ. Đi từ $x$ lên gốc, mỗi lần đi qua một cạnh tới con nhẹ thì kích thước cây con ít nhất gấp đôi, vì con nặng ở cùng cha lớn hơn hoặc bằng con nhẹ đó. Vậy trên đường từ $x$ lên gốc có nhiều nhất $\log_2 n$ cạnh nhẹ, và $x$ bị thêm, xóa $O(\log n)$ lần. Tổng cộng $O(n \log n)$ thao tác trên mảng đếm.

Ví dụHọ Hàng Cùng Bậc

Đề. Rừng $n \le 10^5$ người, mỗi người có nhiều nhất một cha. Có $m \le 10^5$ câu hỏi $(v, p)$ : đếm số người khác $v$ có cùng tổ tiên bậc $p$ với $v$ (tổ tiên bậc $p$ là đỉnh đi lên $p$ lần từ $v$ ); nếu $v$ không có tổ tiên bậc $p$ thì đáp án là $0$ .

Lời giải. Gọi $a$ là tổ tiên bậc $p$ của $v$ . Những người cùng tổ tiên bậc $p$ với $v$ chính là các đỉnh trong cây con của $a$ có cùng độ sâu với $v$ . Vậy câu hỏi trở thành: trong cây con của $a$ , có bao nhiêu đỉnh ở độ sâu $dep_v$ ; trừ đi $1$ cho chính $v$ .

Để tìm $a$ , trong lượt DFS đầu tiên ta giữ mảng $path$ , với $path_d$ là tổ tiên ở độ sâu $d$ của đỉnh đang xét; khi tới $v$ thì $a = path_{dep_v - p}$ nếu $dep_v \ge p$ . Câu hỏi được gắn vào đỉnh $a$ . Lượt DFS thứ hai là sack với mảng đếm theo độ sâu: khi mảng đếm chứa đúng cây con của $a$ , đáp án của câu hỏi là số đỉnh ở độ sâu $dep_v$ trừ $1$ .

Code đầy đủ

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll N = 1e5 + 5;
ll n, m, timer, r[N], dep[N], sz[N], heavy[N], tin[N], tout[N], ord[N], path[N], cnt[N], ans[N];
vector<ll> g[N];
vector<pair<ll, ll>> qs[N], at[N];

void dfs1(ll u) {
    path[dep[u]] = u;
    for (pair<ll, ll> q : qs[u])
        if (dep[u] >= q.first) at[path[dep[u] - q.first]].push_back({dep[u], q.second});
    sz[u] = 1;
    tin[u] = ++timer;
    ord[timer] = u;
    for (ll v : g[u]) {
        dep[v] = dep[u] + 1;
        dfs1(v);
        sz[u] += sz[v];
        if (!heavy[u] || sz[v] > sz[heavy[u]]) heavy[u] = v;
    }
    tout[u] = timer;
}

void dfs2(ll u, bool keep) {
    for (ll v : g[u])
        if (v != heavy[u]) dfs2(v, false);
    if (heavy[u]) dfs2(heavy[u], true);
    for (ll v : g[u])
        if (v != heavy[u])
            for (ll t = tin[v]; t <= tout[v]; t++) cnt[dep[ord[t]]]++;
    cnt[dep[u]]++;
    for (pair<ll, ll> q : at[u]) ans[q.second] = cnt[q.first] - 1;
    if (!keep)
        for (ll t = tin[u]; t <= tout[u]; t++) cnt[dep[ord[t]]]--;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (ll i = 1; i <= n; i++) {
        cin >> r[i];
        if (r[i]) g[r[i]].push_back(i);
    }
    cin >> m;
    for (ll i = 1; i <= m; i++) {
        ll v, p;
        cin >> v >> p;
        qs[v].push_back({p, i});
    }
    for (ll i = 1; i <= n; i++)
        if (!r[i]) dfs1(i);
    for (ll i = 1; i <= n; i++)
        if (!r[i]) dfs2(i, false);
    for (ll i = 1; i <= m; i++) cout << ans[i] << (i == m ? '\n' : ' ');
}

Input8
0 1 1 2 2 0 6 6
6
4 1
4 2
2 2
7 1
6 1
3 1

Output1 1 0 1 0 1

Độ phức tạp: $O((n + m) \log n)$ , với $n = m = 10^5$ cần khoảng $4 \cdot 10^6$ phép tính.

Mảng $path$ dùng chung cho mọi cây của rừng, vì mỗi cây được duyệt riêng và các ô chỉ được đọc sau khi đã ghi trong cùng lượt duyệt. Mỗi cây được gọi dfs2(gốc, false) để mảng đếm sạch trước khi sang cây sau.

IIITruy vấn ngoại tuyến trên cây con

Sack đặc biệt hợp với các câu hỏi biết trước (ngoại tuyến) trên cây con: gom câu hỏi theo đỉnh, và khi mảng đếm vừa chứa đúng cây con của đỉnh đó thì trả lời. Ta chỉ cần biết cách thêm và bớt một đỉnh, và đọc đáp án từ các mảng đang giữ.

Một mẹo hay gặp: khi câu hỏi là “có bao nhiêu màu xuất hiện ít nhất $k$ lần”, ngoài mảng $cnt_c$ (số lần của màu $c$ ) ta giữ thêm $ge_f$ , số màu có ít nhất $f$ lần xuất hiện. Thêm một đỉnh màu $c$ : tăng $cnt_c$ lên $f$ rồi tăng $ge_f$ , vì màu $c$ vừa đạt mốc $f$ . Bớt một đỉnh màu $c$ : giảm $ge_{cnt_c}$ trước rồi mới giảm $cnt_c$ . Cả hai đều $O(1)$ , và đáp án là $ge_k$ .

Ví dụMàu Xuất Hiện Đủ Nhiều

Đề. Cây $n \le 10^5$ đỉnh gốc $1$ , màu mỗi đỉnh tới $10^5$ . Có $q \le 10^5$ câu hỏi $(v, k)$ : trong cây con của $v$ , có bao nhiêu màu xuất hiện ít nhất $k$ lần.

Lời giải. Sack như ví dụ trên, với thao tác thêm, bớt một đỉnh như vừa mô tả. Câu hỏi $(v, k)$ được trả lời ngay khi xử lý xong $v$ ở bước 3. Chú ý $k$ có thể lớn hơn mọi số lần xuất hiện, nên mảng $ge$ cần đủ $10^5 + 1$ ô và các ô lớn mặc định bằng $0$ .

Code đầy đủ

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll N = 1e5 + 5;
ll n, q, timer, c[N], sz[N], heavy[N], tin[N], tout[N], ord[N], cnt[N], ge[N], ans[N];
vector<ll> g[N];
vector<pair<ll, ll>> qs[N];

void dfs1(ll u, ll p) {
    sz[u] = 1;
    tin[u] = ++timer;
    ord[timer] = u;
    for (ll v : g[u])
        if (v != p) {
            dfs1(v, u);
            sz[u] += sz[v];
            if (!heavy[u] || sz[v] > sz[heavy[u]]) heavy[u] = v;
        }
    tout[u] = timer;
}

void add(ll x) {
    ge[++cnt[c[x]]]++;
}

void del(ll x) {
    ge[cnt[c[x]]--]--;
}

void dfs2(ll u, ll p, bool keep) {
    for (ll v : g[u])
        if (v != p && v != heavy[u]) dfs2(v, u, false);
    if (heavy[u]) dfs2(heavy[u], u, true);
    for (ll v : g[u])
        if (v != p && v != heavy[u])
            for (ll t = tin[v]; t <= tout[v]; t++) add(ord[t]);
    add(u);
    for (pair<ll, ll> e : qs[u]) ans[e.second] = ge[e.first];
    if (!keep)
        for (ll t = tin[u]; t <= tout[u]; t++) del(ord[t]);
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> q;
    for (ll i = 1; i <= n; i++) cin >> c[i];
    for (ll i = 1; i < n; i++) {
        ll a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    for (ll i = 1; i <= q; i++) {
        ll v, k;
        cin >> v >> k;
        qs[v].push_back({k, i});
    }
    dfs1(1, 0);
    dfs2(1, 0, true);
    for (ll i = 1; i <= q; i++) cout << ans[i] << '\n';
}

Input7 6
1 2 1 2 3 1 3
1 2
1 3
2 4
2 5
3 6
3 7
1 1
1 2
2 2
3 2
4 1
3 4

Output3
3
1
1
1
0

Độ phức tạp: $O((n + q) \log n)$ , với $n = q = 10^5$ cần khoảng $4 \cdot 10^6$ phép tính.

Hỏi nhanh

Trong hàm del ở trên, một bạn đổi thứ tự thành giảm $cnt_c$ trước rồi mới giảm $ge$ ở ô mới: ge[--cnt[c[x]]]--. Chương trình sai ở đâu?

IVGộp cây phân đoạn

Khi câu hỏi trên cây con phức tạp hơn đếm, chẳng hạn “phần tử nhỏ thứ $k$ trong cây con”, ta có thể cho mỗi đỉnh một cây phân đoạn trên miền giá trị (bài 1.8.1), chỉ tạo những nút thật sự dùng tới, rồi gộp cây của các con vào cha bằng một hàm đệ quy: gộp hai nút cùng vị trí thì gộp hai con trái, gộp hai con phải; một bên rỗng thì lấy luôn bên kia. Mỗi lần gộp hai nút có thật làm mất đi một nút, nên tổng chi phí của mọi lần gộp không vượt quá tổng số nút đã tạo, tức $O(n \log n)$ . Cách này dài hơn sack, nên chỉ dùng khi bảng đếm không đủ để trả lời câu hỏi.

Bài nâng cao

Xem 1 bài nâng cao

Ví dụTên Khác Nhau Ở Đúng Một Tầng

Đề. Rừng $n \le 10^5$ người, mỗi người có một tên (tối đa $20$ chữ cái, có thể trùng nhau). Có $m \le 10^5$ câu hỏi $(v, k)$ : đếm số tên khác nhau của các hậu duệ cách $v$ đúng $k$ đời.

Lời giải. Các hậu duệ cách $v$ đúng $k$ đời là các đỉnh trong cây con của $v$ có độ sâu $dep_v + k$ . Đánh số lại các tên bằng một map từ xâu sang số. Sack với mỗi độ sâu $d$ một map $st_d$ từ tên tới số lần xuất hiện trong cây con đang xét; thêm đỉnh thì tăng, bớt đỉnh thì giảm và xóa tên khi số lần về $0$ . Khi mảng chứa đúng cây con của $v$ , đáp án là số tên trong $st_{dep_v + k}$ , tức là kích thước của map đó. Độ sâu $dep_v + k$ có thể vượt $n$ , khi đó đáp án là $0$ .

Mỗi lần thêm, bớt tốn $O(\log n)$ vì map, nên cả bài tốn $O(n \log^2 n)$ , vẫn đủ nhanh với $n = 10^5$ .

Code đầy đủ

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll N = 1e5 + 5;
ll n, m, timer, r[N], nm[N], dep[N], sz[N], heavy[N], tin[N], tout[N], ord[N], ans[N];
vector<ll> g[N];
vector<pair<ll, ll>> qs[N];
map<string, ll> id;
map<ll, ll> st[2 * N];

void dfs1(ll u) {
    sz[u] = 1;
    tin[u] = ++timer;
    ord[timer] = u;
    for (ll v : g[u]) {
        dep[v] = dep[u] + 1;
        dfs1(v);
        sz[u] += sz[v];
        if (!heavy[u] || sz[v] > sz[heavy[u]]) heavy[u] = v;
    }
    tout[u] = timer;
}

void add(ll x) {
    st[dep[x]][nm[x]]++;
}

void del(ll x) {
    if (--st[dep[x]][nm[x]] == 0) st[dep[x]].erase(nm[x]);
}

void dfs2(ll u, bool keep) {
    for (ll v : g[u])
        if (v != heavy[u]) dfs2(v, false);
    if (heavy[u]) dfs2(heavy[u], true);
    for (ll v : g[u])
        if (v != heavy[u])
            for (ll t = tin[v]; t <= tout[v]; t++) add(ord[t]);
    add(u);
    for (pair<ll, ll> q : qs[u]) {
        ll d = dep[u] + q.first;
        ans[q.second] = d < 2 * N ? st[d].size() : 0;
    }
    if (!keep)
        for (ll t = tin[u]; t <= tout[u]; t++) del(ord[t]);
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (ll i = 1; i <= n; i++) {
        string s;
        cin >> s >> r[i];
        if (!id.count(s)) {
            ll k = id.size() + 1;
            id[s] = k;
        }
        nm[i] = id[s];
        if (r[i]) g[r[i]].push_back(i);
    }
    cin >> m;
    for (ll i = 1; i <= m; i++) {
        ll v, k;
        cin >> v >> k;
        qs[v].push_back({k, i});
    }
    for (ll i = 1; i <= n; i++)
        if (!r[i]) dfs1(i);
    for (ll i = 1; i <= n; i++)
        if (!r[i]) dfs2(i, false);
    for (ll i = 1; i <= m; i++) cout << ans[i] << '\n';
}

Input8
anna 0
bob 1
bob 1
cara 2
dora 2
cara 3
emma 0
bob 7
6
1 1
1 2
2 1
3 1
7 1
4 2

Output1
2
2
1
1
0

Độ phức tạp: $O((n + m) \log^2 n)$ , với $n = m = 10^5$ cần khoảng $3 \cdot 10^7$ phép tính.

Khi đi thi

Bài “với mỗi cây con, thống kê một điều gì đó” mà không có cập nhật: nghĩ tới sack hoặc đổ tập nhỏ vào lớn trước khi nghĩ tới cấu trúc phức tạp. Giá trị nhỏ thì dùng mảng đếm toàn cục với sack; giá trị lớn hay cần thứ tự thì dùng map, set và đổ nhỏ vào lớn.
Lấy bảng của con lớn nhất bằng swap ( $O(1)$ ), không bằng phép gán; đổ xong bảng nhỏ thì xóa nó đi.
Với sack, nhớ rằng chỉ con nặng được giữ lại; mọi con nhẹ đều bị xóa rồi thêm lại, và thứ tự “con nhẹ trước, con nặng sau” là bắt buộc.

Tóm tắt

Đổ tập nhỏ vào tập lớn: mỗi phần tử bị chuyển nhiều nhất $\log_2 n$ lần, vì mỗi lần chuyển bảng chứa nó ít nhất gấp đôi.
Sack giữ lại con nặng, thêm lại các con nhẹ theo đoạn Euler; mỗi đỉnh bị thêm, xóa $O(\log n)$ lần vì đường lên gốc có $O(\log n)$ cạnh nhẹ.
Câu hỏi biết trước trên cây con được gom theo đỉnh và trả lời khi mảng đếm chứa đúng cây con đó.
Đếm số màu đạt ít nhất $k$ lần bằng mảng $ge_f$ cập nhật cùng $cnt_c$ .
Câu hỏi phức tạp hơn đếm thì gộp cây phân đoạn động, tổng $O(n \log n)$ nút.