Tree DP

ITính từ con lên cha

Cây có $n$ đỉnh và đúng $n - 1$ cạnh, giữa hai đỉnh bất kỳ có đúng một đường đi. Sau khi chọn gốc, ta đặt tên các quan hệ: đỉnh ngay phía trên một đỉnh $u$ là cha của $u$, các đỉnh ngay phía dưới là con, và cây con của $u$ gồm $u$ cùng mọi đỉnh nằm dưới nó.

Ví dụ đơn giản nhất của quy hoạch động trên cây là kích thước cây con $\mathrm{sz}[u]$, tức số đỉnh của cây con của $u$. Nó bằng $1$ (chính $u$) cộng kích thước cây con của từng con của $u$. Cái cần cẩn thận duy nhất là thứ tự: khi tính cho $u$, mọi con của $u$ phải đã xong. Hàm đệ quy làm được điều này một cách tự nhiên, nhưng cây có thể là một đường dài $10^5$ đỉnh, và đệ quy sâu chừng ấy tầng có thể làm tràn ngăn xếp. Ta tránh bằng cách duyệt BFS từ gốc, ghi lại thứ tự gặp các đỉnh vào mảng ord và cha của từng đỉnh vào par. Trong thứ tự này, cha luôn đứng trước con của nó, nên nếu đi ngược từ cuối mảng về đầu thì con luôn được xử lý trước cha.

#include <bits/stdc++.h>
using namespace std;
#define ll long long

const ll N = 1e5 + 5;
ll n, par[N], ord[N], sz[N];
vector<ll> g[N];

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    for (ll i = 1; i < n; i++) {
        ll u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    ll m = 0;
    ord[++m] = 1;
    for (ll i = 1; i <= m; i++) {
        ll u = ord[i];
        for (ll v : g[u])
            if (v != par[u]) par[v] = u, ord[++m] = v;
    }
    for (ll i = 1; i <= n; i++) sz[i] = 1;
    for (ll i = n; i >= 2; i--) sz[par[ord[i]]] += sz[ord[i]];
    for (ll i = 1; i <= n; i++) cout << sz[i] << ' ';
    cout << '\n';
}

ChạyInput5
1 2
1 3
2 4
2 5

Output5 3 1 1 1 

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

Ví dụChọn Đại Diện Sửa Đường

Đề. Có $n \le 10^5$ khu vực nối bởi $n - 1$ con đường hai chiều thành một cây, trụ sở ở khu vực $1$. Mỗi đường thuộc loại $1$ (bình thường) hoặc loại $2$ (cần sửa). Chọn một khu vực $v$ nghĩa là cử một người từ $v$ đi theo đường duy nhất về khu vực $1$ và sửa mọi đường loại $2$ trên đường đi. Hãy chọn ít khu vực nhất để mọi đường loại $2$ đều được sửa, rồi in số khu vực và một danh sách.

Lời giải. Treo cây từ khu vực $1$ và xét một đường loại $2$ nối đỉnh $v$ với cha của nó. Người sửa đường này phải xuất phát từ cây con của $v$. Nếu cây con của $v$ đã có một khu vực được chọn, người đó đi về gốc chắc chắn qua đường này, ta không cần làm gì thêm. Nếu chưa có, ta buộc phải chọn thêm một khu vực trong cây con của $v$, và chọn ngay $v$ là không kém: người ở $v$ sửa đúng đường này, còn các đường phía trên mà một người ở sâu hơn sửa được thì người ở $v$ cũng sửa được. Mỗi lần chọn như vậy là bắt buộc nên số lượng là ít nhất.

Vậy trạng thái của $v$ chỉ là một cờ: cây con của $v$ đã có khu vực được chọn hay chưa. Ta duyệt ngược thứ tự BFS; xử lý xong $v$ thì báo lên cha của $v$ nếu cây con của $v$ đã có người. Đề cho in danh sách theo thứ tự bất kỳ, nhưng ta sắp tăng dần cho gọn.

#include <bits/stdc++.h>
using namespace std;
#define ll long long

const ll N = 1e5 + 5;
ll n, par[N], typ[N], ord[N], has[N];
vector<pair<ll, ll> > g[N];
vector<ll> ans;

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    for (ll i = 1; i < n; i++) {
        ll u, v, t;
        cin >> u >> v >> t;
        g[u].push_back(make_pair(v, t));
        g[v].push_back(make_pair(u, t));
    }
    ll m = 0;
    ord[++m] = 1;
    for (ll i = 1; i <= m; i++) {
        ll u = ord[i];
        for (ll j = 0; j < (ll)g[u].size(); j++) {
            ll v = g[u][j].first;
            if (v == par[u]) continue;
            par[v] = u;
            typ[v] = g[u][j].second;
            ord[++m] = v;
        }
    }
    for (ll i = n; i >= 2; i--) {
        ll u = ord[i];
        if (typ[u] == 2 && !has[u]) {
            has[u] = 1;
            ans.push_back(u);
        }
        if (has[u]) has[par[u]] = 1;
    }
    sort(ans.begin(), ans.end());
    cout << ans.size() << '\n';
    for (ll i = 0; i < (ll)ans.size(); i++) cout << ans[i] << ' ';
    cout << '\n';
}

ChạyInput7
1 2 2
2 3 1
2 4 2
1 5 1
5 6 2
6 7 1

Output2
4 6 

Độ phức tạp: $O(n)$ cho BFS và một lượt ngược, với $n = 10^5$ cần khoảng $5 \cdot 10^5$ phép tính, cộng $O(n \log n)$ cho bước sắp xếp danh sách.

IIChọn hoặc không chọn đỉnh gốc của cây con

Ta quay lại bài toán đầu: chọn nhiều đỉnh nhất sao cho không có hai đỉnh được chọn kề nhau. Cách nghĩ vét cạn là thử mọi tập con, $2^n$ phương án. Ta có thể thấy cây con của $u$ chỉ nối với phần còn lại của cây qua một cạnh duy nhất, cạnh từ $u$ lên cha. Vì vậy, muốn biết một cách chọn trong cây con của $u$ có ghép được với cách chọn bên ngoài hay không, chỉ cần biết $u$ có được chọn hay không. Với mỗi đỉnh $u$ ta giữ hai con số:

• $f_1[u]$ là số đỉnh chọn được nhiều nhất trong cây con của $u$ khi $u$ được chọn;
• $f_0[u]$ là số đó khi $u$ không được chọn.

Nếu chọn $u$ thì không con nào của $u$ được chọn, nên $f_1[u]$ bằng $1$ cộng tổng $f_0$ của các con. Nếu không chọn $u$ thì mỗi con tự do chọn hay không, ta lấy cách tốt hơn cho từng con: $f_0[u]$ bằng tổng $\max(f_0[v], f_1[v])$ qua các con $v$. Đáp án là $\max(f_0[1], f_1[1])$. Khi mỗi đỉnh có thêm giá trị thì thay số $1$ bằng giá trị của đỉnh đó.

Chương trình dưới đây tính cho cây trong hình. Mỗi đỉnh lấy dữ liệu từ các con của nó, đi theo thứ tự ngược của BFS.

#include <bits/stdc++.h>
using namespace std;
#define ll long long

const ll N = 1e5 + 5;
ll n, par[N], ord[N], f0[N], f1[N];
vector<ll> g[N];

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    for (ll i = 1; i < n; i++) {
        ll u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    ll m = 0;
    ord[++m] = 1;
    for (ll i = 1; i <= m; i++) {
        ll u = ord[i];
        for (ll v : g[u])
            if (v != par[u]) par[v] = u, ord[++m] = v;
    }
    for (ll i = n; i >= 1; i--) {
        ll u = ord[i];
        f1[u] = 1;
        for (ll v : g[u]) {
            if (v == par[u]) continue;
            f0[u] += max(f0[v], f1[v]);
            f1[u] += f0[v];
        }
    }
    cout << max(f0[1], f1[1]) << '\n';
}

ChạyInput7
1 2
1 3
2 4
2 5
3 6
5 7

Output4

Độ phức tạp: $O(n)$, vì mỗi cạnh được xét hai lần, với $n = 10^5$ cần khoảng $10^6$ phép tính.

Sử dụng kiến thức này cũng có thể giải bài phủ đỉnh nhỏ nhất (chọn ít đỉnh nhất để mỗi cạnh có ít nhất một đầu được chọn): các đỉnh không được chọn khi đó không có hai đỉnh nào kề nhau, nên đáp án bằng $n$ trừ đi kích thước tập độc lập lớn nhất.

Ví dụGhép Cạnh Trên Cây

Đề. Cho một cây $n \le 2 \cdot 10^5$ đỉnh. Chọn nhiều cạnh nhất có thể sao cho không có hai cạnh được chọn cùng đi qua một đỉnh (một cặp ghép của cây). In số cạnh đó.

Lời giải. Cũng hai trạng thái cho mỗi đỉnh $u$, nhưng ý nghĩa khác: $d_0[u]$ là số cạnh nhiều nhất trong cây con của $u$ khi $u$ không ghép với con nào, và $d_1[u]$ là số đó khi $u$ ghép với đúng một con. Đặt $b$ là tổng của $\max(d_0[v], d_1[v])$ qua các con $v$ của $u$. Nếu $u$ không ghép với con nào thì mỗi con tự do chọn, nên $d_0[u] = b$. Nếu $u$ ghép với con $v$ thì cạnh $(u, v)$ được thêm vào, $v$ bắt buộc ở trạng thái chưa ghép với con của nó, còn các con khác tự do:

Đỉnh lá không có con nên không thể ghép xuống; ta gán $d_1 = -10^{18}$ cho nó để trạng thái này không bao giờ được chọn.

#include <bits/stdc++.h>
using namespace std;
#define ll long long

const ll N = 2e5 + 5;
ll n, par[N], ord[N], d0[N], d1[N];
vector<ll> g[N];

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    for (ll i = 1; i < n; i++) {
        ll u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    ll m = 0;
    ord[++m] = 1;
    for (ll i = 1; i <= m; i++) {
        ll u = ord[i];
        for (ll v : g[u])
            if (v != par[u]) par[v] = u, ord[++m] = v;
    }
    for (ll i = n; i >= 1; i--) {
        ll u = ord[i], b = 0;
        for (ll v : g[u])
            if (v != par[u]) b += max(d0[v], d1[v]);
        d0[u] = b;
        d1[u] = -1e18;
        for (ll v : g[u])
            if (v != par[u]) d1[u] = max(d1[u], b - max(d0[v], d1[v]) + d0[v] + 1);
    }
    cout << max(d0[1], d1[1]) << '\n';
}

ChạyInput5
1 2
2 3
2 4
4 5

Output2

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

IIIĐường kính bằng quy hoạch động

Đường kính của cây là đường đi dài nhất giữa hai đỉnh. Cho một cây mà cạnh $(u, v)$ có độ dài $w(u, v) \ge 0$; ta muốn tìm độ dài của đường kính. Hai lần BFS ở bài 3.1 làm được khi mọi cạnh có độ dài $1$; ở đây ta tìm bằng quy hoạch động để dùng được cho độ dài tùy ý không âm.

Mỗi đường đi trên cây treo gốc có một đỉnh cao nhất, là đỉnh gần gốc nhất của nó, và đường đi gồm hai nhánh đi xuống từ đỉnh đó, qua hai con khác nhau (hoặc chỉ một nhánh). Gọi $h[u]$ là độ dài nhánh đi xuống dài nhất từ $u$, $h[u] = 0$ nếu $u$ là lá. Với mỗi con $v$ của $u$, nhánh đi qua $v$ có độ dài $h[v] + w(u, v)$. Hai nhánh tốt nhất qua hai con khác nhau cho đường dài nhất có đỉnh cao nhất là $u$, và đường kính là giá trị lớn nhất của đại lượng này qua mọi $u$.

Để lấy hai nhánh tốt nhất, ta giữ hai biến $m_1 \ge m_2$ khi lướt qua các con: nhánh tốt nhất và nhánh tốt nhì. Khi $u$ có một con thì $m_2 = 0$ và đường kính qua $u$ chỉ là một nhánh.

Ví dụĐồng Nhất Màu Trên Cây

Đề. Cho cây $n \le 2 \cdot 10^5$ đỉnh, mỗi đỉnh có màu $0$ hoặc $1$. Một thao tác chọn một đỉnh $v$ và đảo màu toàn bộ thành phần đơn sắc đang chứa $v$, tức tập các đỉnh nối với $v$ bằng đường đi chỉ gồm đỉnh cùng màu với $v$. Tìm số thao tác ít nhất để mọi đỉnh cùng màu.

Lời giải. Gán cho mỗi cạnh độ dài $1$ nếu hai đầu khác màu và độ dài $0$ nếu cùng màu. Khi đó độ dài của một đường đi là số lần màu đổi dọc đường. Gọi $D$ là đường kính theo độ dài này. Ta sẽ chứng minh đáp án là $\lceil D/2 \rceil$, tức $(D + 1)/2$ với phép chia nguyên.

Còn lại là tính $D$ bằng quy hoạch động ở trên. Với $D = 3$ trong ví dụ mẫu (màu $0, 0, 1, 1, 0, 1$ trên đường $1 - 2 - 3 - 4 - 5 - 6$, màu đổi ba lần), đáp án là $2$.

#include <bits/stdc++.h>
using namespace std;
#define ll long long

const ll N = 2e5 + 5;
ll n, c[N], par[N], ord[N], h[N];
vector<ll> g[N];

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 u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    ll m = 0;
    ord[++m] = 1;
    for (ll i = 1; i <= m; i++) {
        ll u = ord[i];
        for (ll v : g[u])
            if (v != par[u]) par[v] = u, ord[++m] = v;
    }
    ll d = 0;
    for (ll i = n; i >= 1; i--) {
        ll u = ord[i], m1 = 0, m2 = 0;
        for (ll v : g[u]) {
            if (v == par[u]) continue;
            ll x = h[v] + (c[u] != c[v]);
            if (x > m1) m2 = m1, m1 = x;
            else m2 = max(m2, x);
        }
        h[u] = m1;
        d = max(d, m1 + m2);
    }
    cout << (d + 1) / 2 << '\n';
}

ChạyInput6
0 0 1 1 0 1
1 2
2 3
3 4
4 5
5 6

Output2

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

IVHai cây con có giống nhau không

Hai cây con có gốc được gọi là đẳng cấu nếu ta có thể đổi tên các đỉnh của cây này thành đỉnh của cây kia sao cho gốc ứng với gốc và quan hệ cha con được giữ nguyên; nói cách khác chúng giống hệt nhau khi bỏ qua số hiệu đỉnh và thứ tự các con. Muốn so sánh nhiều cây con, ta gán cho mỗi cây con một mã: hai cây con có cùng mã khi và chỉ khi chúng đẳng cấu.

Cây con của $u$ hoàn toàn được xác định bởi các cây con của các con của $u$, và thứ tự các con không quan trọng. Vậy mã của $u$ được xác định bởi đa tập mã của các con (tập có thể lặp phần tử). Ta lấy danh sách mã của các con, sắp xếp tăng dần để thứ tự không ảnh hưởng, rồi tra trong một bảng map từ danh sách sang mã: danh sách đã có thì dùng lại mã cũ, chưa có thì cấp mã mới. Lá có danh sách rỗng nên mọi lá cùng một mã.

Ví dụPhân Lớp Các Cây Con Có Gốc

Đề. Cho cây có gốc $0$ gồm $n \le 5 \cdot 10^5$ đỉnh, đỉnh $v > 0$ có cha $p_v < v$. Hãy chia các cây con có gốc tại từng đỉnh thành các lớp đẳng cấu: in số lớp $k$, rồi $n$ số $c_0, \dots, c_{n-1}$ với $0 \le c_v < k$ sao cho $c_u = c_v$ khi và chỉ khi hai cây con tại $u$ và $v$ đẳng cấu.

Lời giải. Vì cha có chỉ số nhỏ hơn con, đi $v$ từ $n - 1$ xuống $0$ thì mọi con của $v$ đã xong. Mỗi đỉnh xong thì mã của nó được đẩy vào danh sách của cha. Tổng độ dài các danh sách là $n - 1$, bảng map có khoá là danh sách nên mỗi lần tra tốn thời gian tỉ lệ với độ dài danh sách nhân $\log n$.

#include <bits/stdc++.h>
using namespace std;
#define ll long long

const ll N = 5e5 + 5;
ll n, p[N], c[N];
vector<ll> ch[N];
map<vector<ll>, ll> id;

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    for (ll i = 1; i < n; i++) cin >> p[i];
    for (ll v = n - 1; v >= 0; v--) {
        sort(ch[v].begin(), ch[v].end());
        if (!id.count(ch[v])) {
            ll k = id.size();
            id[ch[v]] = k;
        }
        c[v] = id[ch[v]];
        if (v > 0) ch[p[v]].push_back(c[v]);
    }
    cout << id.size() << '\n';
    for (ll v = 0; v < n; v++) cout << c[v] << ' ';
    cout << '\n';
}

ChạyInput7
0 0 1 1 2 2

Output3
2 1 1 0 0 0 0 

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