Euler Tour

Thời điểm vào, ra

Vài chữ về cây. Cây là đồ thị liên thông không có chu trình; cây $n$ đỉnh có đúng $n - 1$ cạnh. Chọn một đỉnh làm gốc thì mỗi đỉnh khác có đúng một cha, là đỉnh kề nó trên đường về gốc.

Các đỉnh nằm phía dưới $u$, kể cả $u$, tạo thành cây con của $u$; trừ chính $u$ ra thì đó là các hậu duệ của $u$. Độ sâu của một đỉnh là số cạnh từ gốc tới nó.

DFS từ gốc, gán tin[u] = ++timer khi vừa vào $u$, và tout[u] = timer khi đã duyệt xong mọi con của $u$. Các đỉnh được đánh số trong lúc ở trong cây con của $u$ chính là các đỉnh của cây con đó, và chúng nhận các số liên tiếp từ $tin_u$ tới $tout_u$. Vậy:

• Cây con của $u$ là đoạn $[tin_u, tout_u]$ trong mảng ord, với ord[tin[u]] = u.
• Kích thước cây con là $sz_u = tout_u - tin_u + 1$.
• $u$ là tổ tiên của $v$ (hoặc $u = v$) khi và chỉ khi $tin_u \le tin_v \le tout_u$.

void dfs(ll u, ll p) {
    tin[u] = ++timer;
    ord[timer] = u;
    for (ll v : g[u])
        if (v != p) dfs(v, u);
    tout[u] = timer;
}

Đệ quy sâu tới $n$ tầng khi cây là một đường. Với $n = 2 \cdot 10^5$ thường vẫn ổn trên máy chấm Linux, nhưng nếu lo tràn ngăn xếp thì tự giữ ngăn xếp.

Ngăn xếp tự giữ chỉ để tránh tràn, không để chạy nhanh hơn:

Hai cách có tốc độ như nhau, đệ quy còn nhanh hơn chút. Cây nông thì cứ đệ quy; cây có thể là một đường dài thì mới đổi.

Ví dụSơ Đồ Cấp Dưới

Đề. Cây $n \le 2 \cdot 10^5$ đỉnh gốc 1, cho cha của mỗi đỉnh $2..n$ (cha không nhất thiết có chỉ số nhỏ hơn). In số hậu duệ của từng đỉnh.

Lời giải. DFS từ 1 gán tin[u] lúc vào và tout[u] lúc ra (số thứ tự lớn nhất trong cây con). Cây con của $u$ chiếm đúng các số $tin_u..tout_u$, nên có $tout_u - tin_u + 1$ đỉnh, và trừ chính $u$ còn $tout_u - tin_u$ hậu duệ. Cha có thể có chỉ số lớn hơn con nên không tính được bằng một vòng lặp ngược chỉ số; DFS lo việc đó.

Bước 1: danh sách con. Đề cho cha của từng đỉnh, nên g[p] chỉ chứa con của $p$ và dfs không cần tham số cha.

for (ll v = 2; v <= n; v++) {
    ll p;
    cin >> p;
    g[p].push_back(v);
}

Bước 2: DFS gán thời điểm.

void dfs(ll u) {
    tin[u] = ++timer;
    for (ll v : g[u]) dfs(v);
    tout[u] = timer;
}

Đệ quy sâu tới $2 \cdot 10^5$ khi cây là một đường; mức đó thường vẫn chạy được, nhưng cây sâu hơn thì phải chuyển sang ngăn xếp tường minh.

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

const ll N = 2e5 + 5;
ll n, timer, tin[N], tout[N];
vector<ll> g[N];

void dfs(ll u) {
    tin[u] = ++timer;
    for (ll v : g[u]) dfs(v);
    tout[u] = timer;
}

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

    cin >> n;
    for (ll v = 2; v <= n; v++) {
        ll p;
        cin >> p;
        g[p].push_back(v);
    }
    dfs(1);
    for (ll u = 1; u <= n; u++) cout << tout[u] - tin[u] << ' ';
    cout << '\n';
}

ChạyInput7
1 1 3 3 5 1

Output6 0 3 0 1 0 0

Độ phức tạp: $O(n)$.

Cây con là đoạn

Đặt giá trị của đỉnh $u$ vào ô $tin_u$ của một mảng. Tổng trên cây con của $u$ là tổng đoạn $[tin_u, tout_u]$; đổi giá trị một đỉnh là sửa một ô. Fenwick (bài 16) trả lời cả hai trong $O(\log n)$.

Thứ tự các con khi DFS quyết định thứ tự trong mảng. Muốn thứ tự cố định (chẳng hạn con nhỏ trước), sắp danh sách con trước khi DFS.

Hai đoạn cây con của hai đỉnh hoặc lồng nhau (một đỉnh là tổ tiên của đỉnh kia) hoặc rời nhau, không bao giờ chồng một phần. Nên kiểm tổ tiên chỉ cần so hai đoạn: $u$ là tổ tiên của $v$ khi $tin_v \in [tin_u, tout_u]$.

Ví dụTổng Trong Cây Con

Đề. Cây $n \le 2 \cdot 10^5$ đỉnh có giá trị, $q \le 2 \cdot 10^5$ thao tác: gán giá trị một đỉnh, hoặc in tổng giá trị trên cây con của một đỉnh.

Lời giải. Trải cây thành mảng theo thứ tự $tin$: cây con của $s$ thành đoạn $[tin_s, tout_s]$. Bài thành “gán một điểm, hỏi tổng một đoạn” trên mảng, giải bằng Fenwick. Tổng tới $2 \cdot 10^{14}$, cần ll.

Bước 1: DFS và đặt giá trị. Sau DFS, đặt a[i] vào ô tin[i] của Fenwick.

dfs(1, 0);
for (ll i = 1; i <= n; i++) update(tin[i], a[i]);

Bước 2: gán. Fenwick chỉ cộng được, nên cộng phần chênh x - a[s] rồi nhớ giá trị mới vào a[s].

update(tin[s], x - a[s]);
a[s] = x;

Bước 3: tổng cây con. Tổng đoạn bằng hai tổng tiền tố.

cout << get(tout[s]) - get(tin[s] - 1) << '\n';

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

const ll N = 2e5 + 5;
ll n, q, timer, a[N], tin[N], tout[N], bit[N];
vector<ll> g[N];

void update(ll pos, ll val) {
    for (; pos <= n; pos += pos & -pos) bit[pos] += val;
}

ll get(ll pos) {
    ll res = 0;
    for (; pos > 0; pos -= pos & -pos) res += bit[pos];
    return res;
}

void dfs(ll u, ll p) {
    tin[u] = ++timer;
    for (ll v : g[u])
        if (v != p) dfs(v, u);
    tout[u] = timer;
}

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

    cin >> n >> q;
    for (ll i = 1; i <= n; i++) cin >> a[i];
    for (ll i = 1; i < n; i++) {
        ll u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(1, 0);
    for (ll i = 1; i <= n; i++) update(tin[i], a[i]);
    while (q--) {
        ll t, s;
        cin >> t >> s;
        if (t == 1) {
            ll x;
            cin >> x;
            update(tin[s], x - a[s]);
            a[s] = x;
        } else cout << get(tout[s]) - get(tin[s] - 1) << '\n';
    }
}

+13 dòngChạyInput6 6
5 1 4 2 7 3
1 2
1 3
2 4
2 5
3 6
2 2
1 5 10
2 1
2 3
1 1 8
2 1

Output10
25
7
28

Độ phức tạp: mỗi thao tác $O(\log n)$.

Đường từ gốc

Tổng trên đường từ gốc tới $s$ là tổng các tổ tiên của $s$ cùng chính nó. Đổi góc nhìn: giá trị của đỉnh $u$ đóng góp vào đáp án của mọi đỉnh trong cây con của $u$. Vậy cộng $a_u$ lên cả đoạn $[tin_u, tout_u]$, và đáp án của $s$ là giá trị tại một điểm $tin_s$. Fenwick trên mảng hiệu làm được cả hai: cộng đoạn là hai lần cộng điểm, hỏi điểm là một tổng tiền tố. Hai cách nhìn “cập nhật điểm, hỏi cây con” và “cập nhật cây con, hỏi điểm” là đối ngẫu của nhau.

Ví dụTổng Trên Đường Từ Gốc

Đề. Cây $n \le 2 \cdot 10^5$ đỉnh có giá trị, $q \le 2 \cdot 10^5$ thao tác: gán giá trị một đỉnh, hoặc in tổng giá trị trên đường từ gốc 1 tới một đỉnh.

Lời giải. Đảo vai: thay vì hỏi tổng của các tổ tiên của $s$, cho mỗi đỉnh $u$ “phát” giá trị $a_u$ xuống cả cây con của nó. Khi đó giá trị nhận được tại $s$ là tổng $a$ của mọi đỉnh có cây con chứa $s$, tức mọi tổ tiên của $s$ và chính $s$. “Cộng cả cây con” là cộng một đoạn $[tin_u, tout_u]$, “đọc giá trị tại $s$” là đọc một điểm: Fenwick trên mảng hiệu làm cả hai trong $O(\log n)$.

Bước 1: cộng một cây con. Mảng hiệu: $+val$ ở đầu đoạn, $-val$ ngay sau cuối đoạn; giá trị tại một điểm là tổng tiền tố tới điểm đó.

void add(ll u, ll val) {
    update(tin[u], val);
    update(tout[u] + 1, -val);
}

Bước 2: khởi tạo và gán. Ban đầu mỗi đỉnh góp a[u] cho cả cây con của mình. Gán giá trị mới thì cộng phần chênh lên đúng cây con của đỉnh đó.

for (ll i = 1; i <= n; i++) add(i, a[i]);

add(s, x - a[s]);
a[s] = x;

Bước 3: câu hỏi. Tổng trên đường từ gốc tới $s$ là get(tin[s]).

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

const ll N = 2e5 + 5;
ll n, q, timer, a[N], tin[N], tout[N], bit[N];
vector<ll> g[N];

void update(ll pos, ll val) {
    for (; pos <= n; pos += pos & -pos) bit[pos] += val;
}

ll get(ll pos) {
    ll res = 0;
    for (; pos > 0; pos -= pos & -pos) res += bit[pos];
    return res;
}

void add(ll u, ll val) {
    update(tin[u], val);
    update(tout[u] + 1, -val);
}

void dfs(ll u, ll p) {
    tin[u] = ++timer;
    for (ll v : g[u])
        if (v != p) dfs(v, u);
    tout[u] = timer;
}

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

    cin >> n >> q;
    for (ll i = 1; i <= n; i++) cin >> a[i];
    for (ll i = 1; i < n; i++) {
        ll u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(1, 0);
    for (ll i = 1; i <= n; i++) add(i, a[i]);
    while (q--) {
        ll t, s;
        cin >> t >> s;
        if (t == 1) {
            ll x;
            cin >> x;
            add(s, x - a[s]);
            a[s] = x;
        } else cout << get(tin[s]) << '\n';
    }
}

+13 dòngChạyInput6 6
5 1 4 2 7 3
1 2
1 3
2 4
2 5
3 6
2 5
1 2 6
2 4
2 6
1 1 1
2 6

Output13
13
12
8

Độ phức tạp: mỗi thao tác $O(\log n)$.

Cập nhật cây con

Khi thao tác sửa mọi đỉnh của một cây con và câu hỏi cũng trên cây con, cả hai đều là đoạn: dùng cây phân đoạn lười (bài 17) trên mảng theo thứ tự $tin$. Đảo trạng thái cả nhánh là đảo một đoạn, gán màu cả nhánh là gán một đoạn, mỗi thao tác $O(\log n)$ dù cây con nhỏ hay lớn.

Độ sâu

Câu hỏi “trong cây con của $u$, ở độ sâu $d$” là giao của hai điều kiện: $tin$ nằm trong $[tin_u, tout_u]$, và độ sâu bằng $d$. Gom các đỉnh theo độ sâu, mỗi nhóm giữ danh sách $tin$ tăng dần (DFS đẩy vào theo thứ tự $tin$ nên tự sắp). Số đỉnh của nhóm $d$ thuộc cây con $u$ là số phần tử của danh sách nằm trong đoạn, tìm bằng hai lần tìm kiếm nhị phân. Các đỉnh cùng độ sâu trong một cây con cũng nằm liền nhau trong danh sách của tầng, nên có thể giữ thêm tổng tiền tố hay mặt nạ XOR theo từng tầng.

Ví dụĐếm Hậu Duệ Theo Độ Sâu

Đề. Cây $n \le 2 \cdot 10^5$ đỉnh gốc 1, $p_v < v$; $q \le 2 \cdot 10^5$ câu hỏi $(u, d)$: đếm số đỉnh trong cây con của $u$ có độ sâu (tính từ gốc) bằng $d$.

Lời giải. Đỉnh độ sâu $d$ trong cây con của $u$ là các đỉnh độ sâu $d$ có tin nằm trong $[tin_u, tout_u]$. Gom tin của các đỉnh theo độ sâu thành từng danh sách đã sắp; mỗi câu hỏi đếm số phần tử của một danh sách nằm trong một đoạn bằng hai lần chặt nhị phân.

Bước 1: DFS gom theo độ sâu. lv[d] chứa các tin của đỉnh độ sâu $d$. DFS gán tin tăng dần và đẩy ngay, nên mỗi danh sách tự sắp tăng.

void dfs(ll u) {
    tin[u] = ++timer;
    lv[dep[u]].push_back(tin[u]);
    for (ll v : g[u]) {
        dep[v] = dep[u] + 1;
        dfs(v);
    }
    tout[u] = timer;
}

Bước 2: đếm trong đoạn. upper_bound(tout) trừ lower_bound(tin) là số phần tử trong $[tin_u, tout_u]$. $d$ nhỏ hơn độ sâu của $u$ hay lớn hơn độ sâu lớn nhất đều tự cho 0, vì danh sách rỗng hoặc không phần tử nào trong đoạn.

cout << upper_bound(lv[d].begin(), lv[d].end(), tout[u]) - lower_bound(lv[d].begin(), lv[d].end(), tin[u]) << '\n';

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

const ll N = 2e5 + 5;
ll n, q, timer, tin[N], tout[N], dep[N];
vector<ll> g[N], lv[N];

void dfs(ll u) {
    tin[u] = ++timer;
    lv[dep[u]].push_back(tin[u]);
    for (ll v : g[u]) {
        dep[v] = dep[u] + 1;
        dfs(v);
    }
    tout[u] = timer;
}

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

    cin >> n;
    for (ll v = 2; v <= n; v++) {
        ll p;
        cin >> p;
        g[p].push_back(v);
    }
    dfs(1);
    cin >> q;
    while (q--) {
        ll u, d;
        cin >> u >> d;
        cout << upper_bound(lv[d].begin(), lv[d].end(), tout[u]) - lower_bound(lv[d].begin(), lv[d].end(), tin[u]) << '\n';
    }
}

ChạyInput9
1 1 2 2 3 3 6 6
6
1 2
2 2
3 3
6 2
6 1
8 3

Output4
2
2
1
0
1

Độ phức tạp: DFS $O(n)$, mỗi câu hỏi $O(\log n)$.

Ngoại tuyến

Khi mọi câu hỏi trên cây con biết trước, chúng là các câu hỏi đoạn trên một dãy tĩnh, và mọi kỹ thuật ngoại tuyến cho dãy đều dùng được: Mo (bài 25), quét đầu phải với Fenwick, gộp nhỏ vào lớn. Đếm số giá trị khác nhau trên đoạn có cách quét quen thuộc: duyệt đầu phải $r$ tăng dần, chỉ giữ dấu 1 ở lần xuất hiện cuối của mỗi giá trị trong $[1, r]$; số giá trị khác nhau trên $[l, r]$ là số dấu 1 trong $[l, r]$.

Ví dụSố Màu Trong Mỗi Cây Con

Đề. Cây $n \le 2 \cdot 10^5$ đỉnh gốc 1, mỗi đỉnh một màu tới $10^9$. In số màu khác nhau trong cây con của từng đỉnh.

Lời giải. Trải cây theo $tin$: câu hỏi của $u$ thành “đếm số màu khác nhau trên đoạn $[tin_u, tout_u]$”. Bài đếm giá trị khác nhau trên đoạn có cách giải ngoại tuyến bằng Fenwick: quét đầu phải $r$ tăng dần, và chỉ đặt dấu 1 ở lần xuất hiện cuối của mỗi màu trong $[1, r]$. Khi đó mỗi màu có mặt trong $[l, r]$ được đếm đúng một lần, bởi dấu nằm trong đoạn.

Bước 1: nén màu và trải cây. Nén bằng sort và lower_bound trên bản sao v, để last dùng được mảng thường. col[tin[u]] là màu theo thứ tự DFS.

sort(v + 1, v + n + 1);
for (ll i = 1; i <= n; i++) c[i] = lower_bound(v + 1, v + n + 1, c[i]) - v;

Bước 2: gom câu hỏi theo đầu phải. Câu hỏi của $u$ là đoạn $[tin_u, tout_u]$, gom vào at[tout[u]].

for (ll u = 1; u <= n; u++) at[tout[u]].push_back(u);

Bước 3: quét. Tới ô $r$ có màu $c$: nếu màu $c$ từng xuất hiện cuối ở last[c] thì xóa dấu ở đó, đặt dấu ở $r$, rồi trả lời mọi câu hỏi có đầu phải $r$ bằng tổng Fenwick trên $[l, r]$.

for (ll r = 1; r <= n; r++) {
    if (last[col[r]]) update(last[col[r]], -1);
    update(r, 1);
    last[col[r]] = r;
    for (ll u : at[r]) ans[u] = get(r) - get(tin[u] - 1);
}

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

const ll N = 2e5 + 5;
ll n, timer, c[N], v[N], tin[N], tout[N], col[N], last[N], bit[N], ans[N];
vector<ll> g[N], at[N];

void update(ll pos, ll val) {
    for (; pos <= n; pos += pos & -pos) bit[pos] += val;
}

ll get(ll pos) {
    ll res = 0;
    for (; pos > 0; pos -= pos & -pos) res += bit[pos];
    return res;
}

void dfs(ll u, ll p) {
    tin[u] = ++timer;
    col[timer] = c[u];
    for (ll w : g[u])
        if (w != p) dfs(w, u);
    tout[u] = timer;
}

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

    cin >> n;
    for (ll i = 1; i <= n; i++) {
        cin >> c[i];
        v[i] = c[i];
    }
    sort(v + 1, v + n + 1);
    for (ll i = 1; i <= n; i++) c[i] = lower_bound(v + 1, v + n + 1, c[i]) - v;
    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 u = 1; u <= n; u++) at[tout[u]].push_back(u);
    for (ll r = 1; r <= n; r++) {
        if (last[col[r]]) update(last[col[r]], -1);
        update(r, 1);
        last[col[r]] = r;
        for (ll u : at[r]) ans[u] = get(r) - get(tin[u] - 1);
    }
    for (ll u = 1; u <= n; u++) cout << ans[u] << ' ';
    cout << '\n';
}

ChạyInput8
1 2 1 3 2 3 3 4
1 2
1 3
2 4
2 5
3 6
6 7
6 8

Output4 2 3 1 1 2 1 1

Độ phức tạp: mỗi ô hai lần cập nhật, mỗi câu hỏi hai tổng tiền tố: $O(n \log n)$.