🌳 Euler Tour trên cây

🎯 Mục tiêu bài học

1. Đặt vấn đề: từ truy vấn trên cây đến truy vấn trên mảng

1.1. Cách làm trực tiếp

Với mỗi truy vấn cây con của u, ta có thể DFS từ u để duyệt toàn bộ hậu duệ. Cách này đúng nhưng trong trường hợp xấu có thể phải đi qua gần như toàn bộ cây.

1.2. Khó khăn cốt lõi

Fenwick Tree, Segment Tree và Prefix Sum đều hoạt động trên mảng, trong khi dữ liệu ban đầu lại là một cây. Vì vậy cần tìm cách đánh số các đỉnh sao cho toàn bộ cây con của một đỉnh trở thành một đoạn liên tiếp.

1.3. Ý tưởng Euler Tour

Ta chạy DFS từ gốc. Ngay khi đi vào một đỉnh u, gán cho nó vị trí tiếp theo trong một mảng. Do DFS luôn duyệt xong toàn bộ cây con của u trước khi quay ra ngoài, các đỉnh trong cây con của u sẽ nằm liên tiếp.

1.4. Ví dụ nhanh

Với cây mẫu, thứ tự vào DFS là:

• Cây con của đỉnh 2 gồm {2,4,5}, tương ứng đoạn [1,3].
• Cây con của đỉnh 3 gồm {3,6,7}, tương ứng đoạn [4,6].
• Cây con của đỉnh 1 là toàn bộ cây, tương ứng đoạn [0,6].

2. Ba cách ghi Euler Tour thường gặp

3. Mô phỏng DFS Euler Tour

Cây mẫu có các cạnh: 1-2, 1-3, 2-4, 2-5, 3-6, 3-7.

4. Cây con trở thành một đoạn

DFS phải duyệt xong toàn bộ hậu duệ của u trước khi quay ra ngoài, nên các đỉnh trong subtree của u nằm liên tiếp.

5. Full Euler Tour và LCA bằng RMQ

Giữa lần xuất hiện đầu tiên của u và v, đỉnh có độ sâu nhỏ nhất chính là LCA.

6. Phân tích thuật toán

7. Code mẫu

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

int n, timerDFS = 0;
vector<vector<int>> adj;
vector<int> tin, tout, flat;

void dfs(int u, int parent) {
    tin[u] = timerDFS;
    flat[timerDFS] = u;
    timerDFS++;

    for (int v : adj[u]) {
        if (v == parent) continue;
        dfs(v, u);
    }

    tout[u] = timerDFS - 1;
}

int main() {
    cin >> n;
    adj.assign(n + 1, {});
    tin.assign(n + 1, 0);
    tout.assign(n + 1, 0);
    flat.assign(n, 0);

    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    dfs(1, 0);
}

struct Event {
    int u, parent;
    bool isExit;
};

void eulerIterative(int root) {
    int timerDFS = 0;
    vector<Event> st;
    st.push_back({root, 0, false});

    while (!st.empty()) {
        Event cur = st.back();
        st.pop_back();

        if (cur.isExit) {
            tout[cur.u] = timerDFS - 1;
            continue;
        }

        tin[cur.u] = timerDFS;
        flat[timerDFS++] = cur.u;

        st.push_back({cur.u, cur.parent, true});

        for (int i = (int)adj[cur.u].size() - 1; i >= 0; i--) {
            int v = adj[cur.u][i];
            if (v == cur.parent) continue;
            st.push_back({v, cur.u, false});
        }
    }
}

vector<int> firstPos, depth;
vector<int> euler, eulerDepth;

void dfsEuler(int u, int parent, int dep) {
    depth[u] = dep;

    if (firstPos[u] == -1)
        firstPos[u] = (int)euler.size();

    euler.push_back(u);
    eulerDepth.push_back(dep);

    for (int v : adj[u]) {
        if (v == parent) continue;

        dfsEuler(v, u, dep + 1);

        euler.push_back(u);
        eulerDepth.push_back(dep);
    }
}

def euler_flatten(adj, root=1):
    n = len(adj) - 1
    tin = [0] * (n + 1)
    tout = [0] * (n + 1)
    flat = [0] * n
    timer = 0

    def dfs(u, parent):
        nonlocal timer

        tin[u] = timer
        flat[timer] = u
        timer += 1

        for v in adj[u]:
            if v != parent:
                dfs(v, u)

        tout[u] = timer - 1

    dfs(root, 0)
    return tin, tout, flat

7.1. Fenwick Tree + Euler Tour

// Lưu value[u] tại vị trí tin[u].
for (int u = 1; u <= n; u++)
    bit.add(tin[u], value[u]);

// Cập nhật giá trị một đỉnh:
bit.add(tin[u], delta);

// Tổng cây con u:
long long subtreeSum = bit.rangeSum(tin[u], tout[u]);

8. Giải thích code

Vì sao gán tin trước khi duyệt con?

tin[u] phải là vị trí đầu tiên của subtree u, nên được gán ngay khi DFS bước vào u.

Vì sao tout = timer − 1?

Sau khi duyệt xong subtree, timer đang chỉ vị trí trống tiếp theo. Vị trí cuối subtree là vị trí trước đó.

Vì sao bỏ qua parent?

Kiểm tra tổ tiên

Vì sao LCA trở thành RMQ?

Trong Full Euler Tour, đoạn giữa first[u] và first[v] mô tả quá trình DFS đi qua vùng nối hai nhánh. Đỉnh có depth nhỏ nhất trên đoạn là tổ tiên chung thấp nhất.

9. Ứng dụng và mở rộng

10. Quiz và bài tập