Euler Tour

Thời điểm vào ra và kích thước cây con

Nhắc lại 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 đi 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.

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;
using 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';
}

Input7
1 1 3 3 5 1

Output6 0 3 0 1 0 0

$O(n)$.

Ví dụQuan Hệ Trên Cây

Đề. Cây $n \le 10^5$ đỉnh gốc 1, $q \le 10^5$ câu hỏi $(u, v)$ với $u \ne v$: in MA nếu $u$ là tổ tiên của $v$, RI nếu $v$ là tổ tiên của $u$, SA nếu không.

Lời giải. Một lần DFS tính $tin$, $tout$; mỗi câu hỏi so hai đoạn trong $O(1)$. Đ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 (hai nhánh khác nhau), không bao giờ chồng một phần.

Bước 1: DFS trên cây cho bằng cạnh. Cạnh thêm vào hai đầu, nên dfs mang theo đỉnh cha để không đi ngược lên.

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

Bước 2: kiểm tổ tiên. $u$ là tổ tiên của $v$ (hoặc chính $v$) khi tin[v] nằm trong đoạn của $u$. Đề cho $u \ne v$ nên không lẫn với trường hợp bằng nhau. Thử hai chiều; cả hai sai là hai nhánh khác nhau.

bool anc(ll u, ll v) {
    return tin[u] <= tin[v] && tin[v] <= tout[u];
}

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

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

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

bool anc(ll u, ll v) {
    return tin[u] <= tin[v] && tin[v] <= tout[u];
}

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

    cin >> n >> q;
    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);
    while (q--) {
        ll u, v;
        cin >> u >> v;
        if (anc(u, v)) cout << "MA\n";
        else if (anc(v, u)) cout << "RI\n";
        else cout << "SA\n";
    }
}

+14 dòngInput8 6
1 2
1 3
2 4
2 5
3 6
6 7
6 8
2 5
5 2
4 5
1 8
7 3
5 8

OutputMA
RI
SA
MA
RI
SA

DFS $O(n)$, mỗi câu hỏi $O(1)$.

Cây con là một đ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ự duyệt cố định (chẳng hạn con nhỏ trước), sắp danh sách con trước khi DFS.

Ví dụVị Trí Trong Cây Con

Đề. Cây $n \le 2 \cdot 10^5$ đỉnh gốc 1, cha $p_v < v$. Preorder là thứ tự thăm đỉnh trước rồi mới lần lượt tới các cây con của nó; ở đây duyệt các con theo chỉ số tăng dần. Mỗi câu hỏi $(u, k)$: in đỉnh thứ $k$ trong preorder của cây con gốc $u$, hoặc $-1$.

Lời giải. Preorder của cả cây là thứ tự các đỉnh theo tin. Preorder của cây con $u$ là đoạn con liền của nó, từ vị trí $tin_u$ tới $tout_u$. Vậy ghi ord[t] là đỉnh có tin = t, và đáp án là ord[tin[u] + k - 1] nếu $k$ không vượt kích thước cây con.

Bước 1: danh sách con đã sắp. Đọc $v$ từ 2 tới $n$ theo thứ tự tăng và đẩy vào g[p], nên danh sách con tự sắp tăng, đúng thứ tự preorder đề đòi.

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

Bước 2: DFS ghi thứ tự.

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

Bước 3: trả lời. tout[u] - tin[u] + 1 là kích thước cây con; $k$ lớn hơn thì in $-1$.

if (k > tout[u] - tin[u] + 1) cout << -1 << '\n';
else cout << ord[tin[u] + k - 1] << '\n';

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

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

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

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

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

Input9 7
1 1 2 2 3 3 6 6
1 1
1 6
2 3
3 4
6 3
6 4
7 1

Output1
6
5
9
9
-1
7

DFS $O(n)$, mỗi câu hỏi $O(1)$.

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;
using 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òngInput6 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

Mỗi thao tác $O(\log n)$.

Đường từ gốc: cập nhật cây con, hỏi điểm

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;
using 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òngInput6 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

Mỗi thao tác $O(\log n)$.

Cập nhật cả 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: 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. Cây con nhỏ hay lớn đều tốn $O(\log n)$.

Ví dụĐảo Trạng Thái Trong Nhánh

Đề. Cây $n \le 2 \cdot 10^5$ đỉnh, mỗi đỉnh bật hoặc tắt. $q \le 2 \cdot 10^5$ lệnh: pow v đảo mọi đỉnh trong cây con của $v$, get v đếm số đỉnh bật trong cây con của $v$.

Lời giải. Trải cây theo $tin$: pow v thành “đảo mọi phần tử của đoạn $[tin_v, tout_v]$”, get v thành “đếm số 1 trên đoạn đó”. Đây đúng là bài “Dãy Công Tắc” của bài 17, chạy trên mảng trải phẳng.

Bước 1: trải trạng thái theo DFS. val[tin[u]] = t[u], rồi build dựng cây phân đoạn trên mảng đó.

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

Bước 2: thẻ đảo. Đảo cả đoạn của một nút: số đỉnh bật thành độ dài trừ số bật, và lật cờ lz để nhớ hai con chưa bị đảo. Hai lần đảo triệt tiêu nhau nên cờ là XOR.

void apply(ll id, ll l, ll r) {
    st[id] = (r - l + 1) - st[id];
    lz[id] ^= 1;
}

void down(ll id, ll l, ll r) {
    if (!lz[id]) return;
    ll mid = (l + r) >> 1;
    apply(id * 2, l, mid);
    apply(id * 2 + 1, mid + 1, r);
    lz[id] = 0;
}

Bước 3: hai lệnh. update và get là cây lười chuẩn trên đoạn $[tin_v, tout_v]$.

if (op == "pow") update(1, 1, n, tin[v], tout[v]);
else cout << get(1, 1, n, tin[v], tout[v]) << '\n';

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

const ll N = 2e5 + 5;
ll n, q, timer, t[N], tin[N], tout[N], val[N], st[4 * N], lz[4 * N];
vector<ll> g[N];

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

void build(ll id, ll l, ll r) {
    if (l == r) {
        st[id] = val[l];
        return;
    }
    ll mid = (l + r) >> 1;
    build(id * 2, l, mid);
    build(id * 2 + 1, mid + 1, r);
    st[id] = st[id * 2] + st[id * 2 + 1];
}

void apply(ll id, ll l, ll r) {
    st[id] = (r - l + 1) - st[id];
    lz[id] ^= 1;
}

void down(ll id, ll l, ll r) {
    if (!lz[id]) return;
    ll mid = (l + r) >> 1;
    apply(id * 2, l, mid);
    apply(id * 2 + 1, mid + 1, r);
    lz[id] = 0;
}

void update(ll id, ll l, ll r, ll u, ll v) {
    if (v < l || r < u) return;
    if (u <= l && r <= v) {
        apply(id, l, r);
        return;
    }
    down(id, l, r);
    ll mid = (l + r) >> 1;
    update(id * 2, l, mid, u, v);
    update(id * 2 + 1, mid + 1, r, u, v);
    st[id] = st[id * 2] + st[id * 2 + 1];
}

ll get(ll id, ll l, ll r, ll u, ll v) {
    if (v < l || r < u) return 0;
    if (u <= l && r <= v) return st[id];
    down(id, l, r);
    ll mid = (l + r) >> 1;
    return get(id * 2, l, mid, u, v) + get(id * 2 + 1, mid + 1, r, u, v);
}

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);
    }
    for (ll i = 1; i <= n; i++) cin >> t[i];
    dfs(1);
    build(1, 1, n);
    cin >> q;
    while (q--) {
        string op;
        ll v;
        cin >> op >> v;
        if (op == "pow") update(1, 1, n, tin[v], tout[v]);
        else cout << get(1, 1, n, tin[v], tout[v]) << '\n';
    }
}

+13 dòngInput7
1 1 2 2 3 6
1 0 1 1 0 0 1
9
get 1
get 2
pow 2
get 2
pow 1
get 1
get 3
pow 6
get 6

Output4
1
2
2
1
1

Mỗi lệnh $O(\log n)$.

Thêm chiều độ 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;
using 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';
    }
}

Input9
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

DFS $O(n)$, mỗi câu hỏi $O(\log n)$.

Câu hỏi đoạn ngoại tuyến trên mảng Euler

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;
using 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';
}

Input8
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

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)$.