Euler tour trên cây (thời điểm vào/ra)

Euler tour trên cây (còn gọi là duỗi cây, DFS order, thời điểm vào/ra) là kỹ thuật đánh số các đỉnh theo thứ tự DFS thăm chúng, sao cho mỗi cây con trở thành một đoạn liên tục trên một mảng. Nhờ đó mọi bài "cập nhật/truy vấn trên cây con" hay "trên đường đi từ gốc" được đưa về bài toán trên mảng và giải bằng Fenwick Tree hoặc Segment Tree: mỗi thao tác $O(\log N)$ thay vì $O(N)$ khi duyệt lại cây con, sau đúng một lần DFS $O(N)$.

Ý tưởng / Trực giác

Chạy DFS từ gốc và giữ một bộ đếm thời gian timer. Khi bước vào đỉnh $u$, tăng timer và ghi tin[u] = timer. Khi rời khỏi $u$ (đã duyệt xong mọi con), ghi tout[u] bằng giá trị timer hiện tại, tức là thời điểm vào lớn nhất trong cây con của $u$.

Vì sao cây con thành một đoạn liên tục? Vì DFS có tính chất "vào rồi mới ra": từ lúc vào $u$ đến lúc rời $u$, DFS chỉ đi lại bên trong cây con của $u$, và mọi đỉnh trong cây con đều được vào trong khoảng thời gian đó. Không đỉnh nào ngoài cây con được vào xen giữa, vì muốn tới một đỉnh ngoài thì DFS phải quay lên qua $u$ trước, tức là đã rời $u$. Do đó:

$$\text{cây con của }u=\{v:\text{tin}[u]\le \text{tin}[v]\le \text{tout}[u]\},|\text{cây con}|=\text{tout}[u]-\text{tin}[u]+1.$$

Hai hệ quả dùng liên tục:

• Kiểm tra tổ tiên trong $O(1)$: $u$ là tổ tiên của $v$ (tính cả $u=v$) khi và chỉ khi tin[u] <= tin[v] && tout[v] <= tout[u]. Hai đoạn $[\text{tin},\text{tout}]$ của hai đỉnh bất kỳ hoặc lồng nhau, hoặc rời nhau, không bao giờ giao một phần (giống dãy ngoặc đúng).
• Đổi góc nhìn "cây con" và "đường đi từ gốc": đỉnh $v$ nằm trong cây con của $u$ $\iff$ $u$ nằm trên đường đi gốc $\to v$. Vì vậy một thao tác trên đường đi gốc $\to v$ có thể viết lại thành thao tác trên các đoạn $[\text{tin}[u],\text{tout}[u]]$ chứa vị trí $\text{tin}[v]$.

Từ đó có hai "chế độ" dùng Fenwick trên mảng duỗi:

Ở dòng thứ hai, điểm $\text{tin}[v]$ nằm trong đoạn của $u$ đúng khi $u$ là tổ tiên của $v$, nên giá trị điểm tại $\text{tin}[v]$ chính là tổng các giá trị trên đường gốc $\to v$.

Ví dụ chạy tay

Cây 8 đỉnh, gốc 1, giá trị ghi trong ngoặc. DFS thăm con theo thứ tự tăng dần số hiệu.

                1(3)
            /    |    \
         2(1)   3(4)   4(1)
        /   \            \
     5(5)   6(9)         7(2)
             |
            8(6)

Bước 1: DFS và ghi thời điểm. Thứ tự vào: 1, 2, 5, 6, 8, 3, 4, 7.

timer:   1   2   3   4   5   6   7   8
vào:     1   2   5   6   8   3   4   7        <- order[timer]
giá trị: 3   1   5   9   6   4   1   2        <- mảng duỗi A[timer] = val[order[timer]]

Đọc bảng: rời đỉnh 8 lúc timer đang là 5 nên tout[8] = 5; rời 6 ngay sau đó, vẫn 5; rời 2 cũng 5. Lá luôn có tin = tout.

Bước 2: truy vấn cây con của 2. Đoạn $[\text{tin}[2],\text{tout}[2]]=[2,5]$:

vị trí:  1   2   3   4   5   6   7   8
đỉnh:    1  [2   5   6   8]  3   4   7
giá trị: 3  [1   5   9   6]  4   1   2
              ^-----------^
              tổng = 1 + 5 + 9 + 6 = 21   (đúng: cây con của 2 là {2, 5, 6, 8})

Bước 3: kiểm tra tổ tiên. 2 có phải tổ tiên của 8? $\text{tin}[2]=2\le 5=\text{tin}[8]$ và $\text{tout}[8]=5\le 5=\text{tout}[2]$: đúng. 3 có phải tổ tiên của 8? $\text{tin}[3]=6>5$: không.

Bước 4: tổng đường đi gốc $\to 8$ bằng "cộng đoạn, hỏi điểm". Mỗi đỉnh $u$ cộng giá trị của nó cho cả đoạn $[\text{tin}[u],\text{tout}[u]]$. Hỏi điểm tại $\text{tin}[8]=5$: những đoạn phủ vị trí 5 là

vị trí:        1   2   3   4   5   6   7   8
đỉnh 1 [1,8]:  +3  +3  +3  +3  +3  +3  +3  +3
đỉnh 2 [2,5]:      +1  +1  +1  +1
đỉnh 6 [4,5]:              +9  +9
đỉnh 8 [5,5]:                  +6
                               ^ điểm 5: 3 + 1 + 9 + 6 = 19

(các đỉnh 3, 4, 5, 7 có đoạn không chứa vị trí 5). Đúng là tổng trên đường $1\to 2\to 6\to 8$.

Bước 5: tổng đường đi $5\to 8$. Gọi $S(v)$ là tổng đường gốc $\to v$ và $w=\text{lca}(5,8)=2$:

$$\text{sum}(5,8)=S(5)+S(8)-2S(2)+\text{val}[2]=9+19-2·4+1=21,$$

khớp với $5+1+9+6$ trên đường $5\to 2\to 6\to 8$. Trừ $2S(w)$ loại phần chung từ gốc tới $w$ bị đếm hai lần, rồi cộng lại $\text{val}[w]$ vì chính $w$ nằm trên đường đi.

Ba dạng Euler tour

Cùng một lần DFS, có ba cách "ghi sổ" khác nhau, mỗi cách hợp với một loại bài.

Dạng A (n phần tử, ghi khi vào):
  1 2 5 6 8 3 4 7

Dạng B (2n phần tử, ghi khi vào VÀ khi ra):
  pos: 1  2  3  4  5  6  7  8  9  10 11 12 13 14 15 16
       1+ 2+ 5+ 5- 6+ 8+ 8- 6- 2- 3+ 3- 4+ 7+ 7- 4- 1-

Dạng C (2n-1 phần tử, ghi mỗi lần "đứng" ở một đỉnh):
  idx: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
       1 2 5 2 6 8 6 2 1 3 1  4  7  4  1

Dạng B trên ví dụ. Đặt $+\text{val}[v]$ tại vị trí vào, $-\text{val}[v]$ tại vị trí ra. Tổng tiền tố tới vị trí vào của $v$ bằng tổng đường gốc $\to v$: những đỉnh đã "vào" mà chưa "ra" tại thời điểm đó chính là các tổ tiên của $v$ (tính cả $v$), các đỉnh đã ra thì $+a$ và $-a$ triệt tiêu. Với $v=7$ (vào ở vị trí 13):

pos:   1  2  3  4  5  6  7  8  9  10 11 12 13
      +3 +1 +5 -5 +9 +6 -6 -9 -1 +4 -4 +1 +2   => tổng = 6 = 3 + 1 + 2 (đường 1 -> 4 -> 7)

Với bài tổng đường gốc $\to v$, dạng B và dạng A (cộng đoạn, hỏi điểm) là tương đương: dạng A cài bằng mảng hiệu cũng chỉ là 2 lần cập nhật điểm (tại $\text{tin}[u]$ và $\text{tout}[u]+1$) cộng 1 lần hỏi tiền tố, y như dạng B (tại vị trí vào và vị trí ra). Cả hai cùng cần phép gộp có nghịch đảo (cộng, XOR, cộng modulo; không dùng được cho max/min). Dạng B chỉ khác ở cách đặt chỉ số: vị trí "hủy" là một ô riêng lúc ra khỏi đỉnh, đổi lại mảng dài gấp đôi.

Dạng C trên ví dụ. $\text{lca}(8,7)$: lần đầu gặp 8 ở idx 5, gặp 7 ở idx 12; đoạn 8 6 2 1 3 1 4 7 có đỉnh nông nhất là 1. Đúng vì DFS đi từ 8 sang 7 buộc phải quay lên qua LCA và không lên cao hơn. Chi tiết về các cách tính LCA xem trang LCA.

Cài đặt

C++: DFS không đệ quy + Fenwick cho cây con, đường gốc, đường $u$-$v$

Chương trình dưới xử lý năm loại truy vấn trên cây gốc 1: 1 s x gán giá trị đỉnh $s$ bằng $x$; 2 s tổng cây con của $s$; 3 s tổng đường gốc $\to s$; 4 u v tổng đường $u\to v$; 5 u v hỏi $u$ có là tổ tiên của $v$. Chỉ giữ loại 1 và 2 là lời giải bài subqry. Bài pathqry ứng với loại 1 và loại 3 ở đây, nhưng trong đề pathqry truy vấn tổng đường gốc được đánh số là loại 2 (2 s): nếu nộp phải đổi nhánh type == 3 thành type == 2, hoặc dùng chương trình dạng $2n$ bên dưới, vốn viết đúng định dạng pathqry.

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

struct Fenwick {
    int n; vector<long long> t;
    Fenwick(int n) : n(n), t(n + 1, 0) {}
    void add(int i, long long d) { for (; i <= n; i += i & -i) t[i] += d; }
    long long pref(int i) const { long long s = 0; for (; i > 0; i -= i & -i) s += t[i]; return s; }
    long long range(int l, int r) const { return pref(r) - pref(l - 1); }
};

int n, q, LOG;
vector<vector<int>> adj, up;
vector<int> tin, tout, order_, dep;

// Iterative DFS: no recursion, safe for n up to 1e6.
void euler_tour(int root) {
    tin.assign(n + 1, 0); tout.assign(n + 1, 0);
    order_.assign(n + 1, 0); dep.assign(n + 1, 0);
    vector<int> par(n + 1, 0), it(n + 1, 0), st;
    int timer = 0;
    st.push_back(root);
    tin[root] = ++timer; order_[timer] = root;
    while (!st.empty()) {
        int u = st.back();
        if (it[u] < (int)adj[u].size()) {
            int v = adj[u][it[u]++];
            if (v == par[u]) continue;
            par[v] = u; dep[v] = dep[u] + 1;
            tin[v] = ++timer; order_[timer] = v;   // enter v
            st.push_back(v);
        } else {
            tout[u] = timer;                       // leave u: last tin inside its subtree
            st.pop_back();
        }
    }
    // Binary lifting table; parent of root is root itself.
    LOG = 1; while ((1 << LOG) < n) LOG++;
    up.assign(LOG, vector<int>(n + 1));
    for (int v = 1; v <= n; v++) up[0][v] = par[v] ? par[v] : v;
    for (int j = 1; j < LOG; j++)
        for (int v = 1; v <= n; v++) up[j][v] = up[j - 1][up[j - 1][v]];
}

// u is an ancestor of v (u == v counts)
bool is_anc(int u, int v) { return tin[u] <= tin[v] && tout[v] <= tout[u]; }

int lca(int u, int v) {
    if (is_anc(u, v)) return u;
    if (is_anc(v, u)) return v;
    for (int j = LOG - 1; j >= 0; j--)
        if (!is_anc(up[j][u], v)) u = up[j][u];
    return up[0][u];
}

int main() {
    scanf("%d %d", &n, &q);
    vector<long long> val(n + 1);
    for (int i = 1; i <= n; i++) scanf("%lld", &val[i]);
    adj.assign(n + 1, {});
    for (int i = 0; i < n - 1; i++) {
        int a, b; scanf("%d %d", &a, &b);
        adj[a].push_back(b); adj[b].push_back(a);
    }
    euler_tour(1);

    Fenwick sub(n);   // point value at tin[v]      -> subtree sum = range query
    Fenwick path(n);  // val[v] added on [tin, tout] -> root path sum = point query
    for (int v = 1; v <= n; v++) {
        sub.add(tin[v], val[v]);
        path.add(tin[v], val[v]); path.add(tout[v] + 1, -val[v]);
    }
    auto root_path = [&](int v) { return path.pref(tin[v]); };

    while (q--) {
        int type; scanf("%d", &type);
        if (type == 1) {                 // set val[s] = x
            int s; long long x; scanf("%d %lld", &s, &x);
            long long d = x - val[s]; val[s] = x;
            sub.add(tin[s], d);
            path.add(tin[s], d); path.add(tout[s] + 1, -d);
        } else if (type == 2) {          // sum over subtree of s
            int s; scanf("%d", &s);
            printf("%lld\n", sub.range(tin[s], tout[s]));
        } else if (type == 3) {          // sum on path root -> s
            int s; scanf("%d", &s);
            printf("%lld\n", root_path(s));
        } else if (type == 4) {          // sum on path u -> v
            int u, v; scanf("%d %d", &u, &v);
            int w = lca(u, v);
            printf("%lld\n", root_path(u) + root_path(v) - 2 * root_path(w) + val[w]);
        } else {                         // is u an ancestor of v?
            int u, v; scanf("%d %d", &u, &v);
            puts(is_anc(u, v) ? "YES" : "NO");
        }
    }
}

Vài điểm đáng chú ý:

• it[u] nhớ "đã duyệt tới cạnh thứ mấy của $u$", nên mỗi đỉnh nằm trên ngăn xếp đúng một lần và thời điểm rời $u$ được xác định rõ (khi hết cạnh). Đây là cách viết lại DFS đệ quy một cách trung thành nhất.
• path.add(tout[v] + 1, ...) có thể chạm vị trí $n+1$; hàm add tự bỏ qua vì vòng lặp dừng khi i > n.
• Hàm lca dùng chính phép kiểm tra tổ tiên: nhảy $u$ lên chừng nào đỉnh đích chưa là tổ tiên của $v$, không cần so độ sâu.

C++: LCA bằng Euler tour $2n-1$ + sparse table

// Euler tour of size 2n-1: write u on entering and again after returning from each child.
struct EulerLCA {
    vector<int> first, dep, tour;   // first[u] = first index of u in tour
    vector<vector<int>> sp;         // sparse table of vertices, min by depth
    int better(int a, int b) const { return dep[a] < dep[b] ? a : b; }

    EulerLCA(const vector<vector<int>>& adj, int root) {
        int n = adj.size() - 1;
        first.assign(n + 1, -1); dep.assign(n + 1, 0);
        vector<int> par(n + 1, 0), it(n + 1, 0), st = {root};
        first[root] = 0; tour.push_back(root);
        while (!st.empty()) {
            int u = st.back();
            if (it[u] < (int)adj[u].size()) {
                int v = adj[u][it[u]++];
                if (v == par[u]) continue;
                par[v] = u; dep[v] = dep[u] + 1;
                first[v] = tour.size(); tour.push_back(v);
                st.push_back(v);
            } else {
                st.pop_back();
                if (!st.empty()) tour.push_back(st.back());  // back at parent
            }
        }
        int m = tour.size(), K = 1;
        while ((1 << K) <= m) K++;
        sp.assign(K, vector<int>(m));
        sp[0] = tour;
        for (int j = 1; j < K; j++)
            for (int i = 0; i + (1 << j) <= m; i++)
                sp[j][i] = better(sp[j - 1][i], sp[j - 1][i + (1 << (j - 1))]);
    }
    int lca(int u, int v) const {
        int l = first[u], r = first[v];
        if (l > r) swap(l, r);
        int j = __lg(r - l + 1);
        return better(sp[j][l], sp[j][r - (1 << j) + 1]);
    }
};

C++: dạng $2n$ cho tổng đường gốc $\to v$ (bài pathqry)

So với chương trình chính chỉ có hai chỗ khác: lúc ra khỏi đỉnh cũng tăng bộ đếm (tout[u] = ++timer thay cho tout[u] = timer), và Fenwick có kích thước $2n$, đặt $+\text{val}$ tại tin, $-\text{val}$ tại tout. Chương trình dưới chạy độc lập, đúng định dạng đề pathqry (1 s x gán, 2 s hỏi tổng đường gốc $\to s$) và không cần bảng nâng nhị phân.

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

struct Fenwick {
    int n; vector<long long> t;
    Fenwick(int n) : n(n), t(n + 1, 0) {}
    void add(int i, long long d) { for (; i <= n; i += i & -i) t[i] += d; }
    long long pref(int i) const { long long s = 0; for (; i > 0; i -= i & -i) s += t[i]; return s; }
};

int main() {
    int n, q;
    scanf("%d %d", &n, &q);
    vector<long long> val(n + 1);
    for (int i = 1; i <= n; i++) scanf("%lld", &val[i]);
    vector<vector<int>> adj(n + 1);
    for (int i = 0; i < n - 1; i++) {
        int a, b; scanf("%d %d", &a, &b);
        adj[a].push_back(b); adj[b].push_back(a);
    }

    // Iterative DFS; timer ticks on both enter and leave, positions 1..2n
    vector<int> tin(n + 1), tout(n + 1), par(n + 1, 0), it(n + 1, 0), st = {1};
    int timer = 0;
    tin[1] = ++timer;
    while (!st.empty()) {
        int u = st.back();
        if (it[u] < (int)adj[u].size()) {
            int v = adj[u][it[u]++];
            if (v == par[u]) continue;
            par[v] = u;
            tin[v] = ++timer;            // enter v
            st.push_back(v);
        } else {
            tout[u] = ++timer;           // leave u: its own position
            st.pop_back();
        }
    }

    Fenwick f(2 * n);                    // +val at tin, -val at tout
    for (int v = 1; v <= n; v++) { f.add(tin[v], val[v]); f.add(tout[v], -val[v]); }

    while (q--) {
        int type, s; scanf("%d %d", &type, &s);
        if (type == 1) {                 // set val[s] = x
            long long x; scanf("%lld", &x);
            long long d = x - val[s]; val[s] = x;
            f.add(tin[s], d); f.add(tout[s], -d);
        } else {                         // sum on path root -> s
            printf("%lld\n", f.pref(tin[s]));
        }
    }
}

Python: tổng cây con có cập nhật (bài subqry)

Python dễ tràn đệ quy (giới hạn mặc định 1000 tầng), nên dùng ngăn xếp. Ở đây dùng một biến thể gọn hơn: lấy thứ tự tiền thứ tự (preorder) bằng ngăn xếp, tính kích thước cây con bằng cách duyệt ngược thứ tự đó, rồi tout = tin + size - 1.

import sys

def main():
    data = sys.stdin.buffer.read().split()
    n, q = int(data[0]), int(data[1])
    val = [0] + [int(x) for x in data[2:2 + n]]
    pos = 2 + n
    adj = [[] for _ in range(n + 1)]
    for _ in range(n - 1):
        a, b = int(data[pos]), int(data[pos + 1]); pos += 2
        adj[a].append(b); adj[b].append(a)

    # Iterative preorder: tin = position in order, tout = tin + size - 1
    tin = [0] * (n + 1); par = [0] * (n + 1); order = []
    stack = [1]; par[1] = -1
    while stack:
        u = stack.pop()
        tin[u] = len(order) + 1
        order.append(u)
        for v in adj[u]:
            if v != par[u]:
                par[v] = u
                stack.append(v)
    size = [1] * (n + 1)
    for u in reversed(order):          # children appear after parent in preorder
        if par[u] > 0:
            size[par[u]] += size[u]
    tout = [tin[u] + size[u] - 1 for u in range(n + 1)]

    bit = [0] * (n + 1)
    def add(i, d):
        while i <= n:
            bit[i] += d; i += i & -i
    def pref(i):
        s = 0
        while i > 0:
            s += bit[i]; i -= i & -i
        return s
    # O(n) Fenwick build from the flattened array
    for u in range(1, n + 1):
        bit[tin[u]] += val[u]
    for i in range(1, n + 1):
        j = i + (i & -i)
        if j <= n:
            bit[j] += bit[i]

    out = []
    for _ in range(q):
        t = data[pos]
        if t == b'1':
            s, x = int(data[pos + 1]), int(data[pos + 2]); pos += 3
            add(tin[s], x - val[s]); val[s] = x
        else:
            s = int(data[pos + 1]); pos += 2
            out.append(pref(tout[s]) - pref(tin[s] - 1))
    sys.stdout.write("\n".join(map(str, out)) + ("\n" if out else ""))

main()

Cách "lấy ra một đỉnh, đẩy mọi con vào" vẫn cho một thứ tự tiền thứ tự hợp lệ: khi một con được lấy ra, toàn bộ cây con của nó được xử lý xong trước khi tới anh em nằm sâu hơn trong ngăn xếp. Chỉ có điều ở cách này không có thời điểm "rời đỉnh" rõ ràng, nên tout phải tính qua kích thước cây con.

Độ phức tạp

• DFS: $O(N)$ thời gian, vì mỗi cạnh được xét hai lần (một lần từ mỗi đầu). Bộ nhớ $O(N)$ cho tin, tout, order, ngăn xếp và con trỏ it.
• Mỗi truy vấn / cập nhật cây con hoặc đường gốc: $O(\log N)$, vì đã quy về một hoặc hai thao tác Fenwick trên mảng độ dài $N$ (dạng $2N$ cũng vẫn $O(\log N)$).
• Đường đi $u$-$v$: thêm chi phí LCA. Nâng nhị phân tốn $O(N\log N)$ bộ nhớ và $O(\log N)$ mỗi truy vấn; Euler tour $2N-1$ + sparse table tốn $O(N\log N)$ tiền xử lý và bộ nhớ, $O(1)$ mỗi truy vấn.
• Dựng Fenwick ban đầu: các chương trình C++ ở trên gọi add $N$ lần nên tốn $O(N\log N)$; có thể hạ xuống $O(N)$ bằng cách dựng thẳng từ mảng duỗi như bản Python.
• Tổng: $O((N+Q)\log N)$ (hoặc $O(N+Q\log N)$ nếu dựng Fenwick trong $O(N)$), không tính phần LCA; so với $O(NQ)$ nếu mỗi truy vấn duyệt lại cây con. Với $N=Q={10}^6$ trên cây là đường thẳng (DFS sâu ${10}^6$ tầng), chương trình C++ chính ở trên chạy khoảng 0,7 giây trên máy thử nhưng dùng khoảng 184 MB bộ nhớ, phần lớn là bảng nâng nhị phân $20\times {10}^6$ số int. Khi không cần hỏi đường $u$-$v$, bỏ bảng up để tiết kiệm bộ nhớ.

⚠️ Lỗi thường gặp

• Nhầm chỉ số đỉnh với chỉ số trên mảng duỗi. Triệu chứng: kết quả sai ngay trên ví dụ. Fenwick được đánh số theo vị trí ($\text{tin}$), nên phải add(tin[v], ...), không phải add(v, ...). Khi dựng mảng ban đầu, A[tin[v]] = val[v] (hoặc A[i] = val[order[i]]).
• Tràn ngăn xếp khi DFS đệ quy. Cây dạng đường thẳng với $N=2·{10}^5$ đến ${10}^6$ cho độ sâu bằng $N$; nhiều máy chấm (nhất là Windows, ngăn xếp mặc định 1 MB) báo Runtime Error. Dùng DFS không đệ quy như trên. Trong Python, sys.setrecursionlimit lớn thường vẫn chết vì hết ngăn xếp C, nên luôn dùng ngăn xếp tay.
• Trộn định nghĩa tout của hai dạng. Ở dạng $n$ phần tử, tout[u] là $\text{tin}$ lớn nhất trong cây con (không tăng timer khi ra); ở dạng $2n$, tout[u] là một vị trí riêng. Dùng tout của dạng $2n$ cho truy vấn đoạn cây con, hoặc quên cấp Fenwick kích thước $2n$, gây lệch chỉ số hoặc truy cập ngoài mảng.
• Hỏi tổng cây con trên dạng $2n$ có dấu $\pm$. Trong đoạn $[\text{tin}[u],\text{tout}[u]]$ của dạng $2n$, mỗi đỉnh con đóng góp $+a$ rồi $-a$, nên tổng luôn bằng $0$. Dạng $\pm$ chỉ dành cho tiền tố (đường gốc $\to v$); muốn hỏi cây con hãy dùng dạng $n$ phần tử (hoặc dạng $2n$ không dấu rồi chia đôi).
• Quên điểm cuối khi cộng đoạn. Cộng đoạn bằng mảng hiệu cần add(tin[u], x) và add(tout[u] + 1, -x). Thiếu vế sau thì giá trị "tràn" sang mọi cây con phía sau.
• Đường $u$-$v$ bị đếm sai đỉnh LCA. Công thức với giá trị trên đỉnh: $S(u)+S(v)-2S(w)+\text{val}[w]$. Nếu giá trị nằm trên cạnh (lưu trọng số cạnh $(p,c)$ ở đỉnh con $c$), thì công thức là $S(u)+S(v)-2S(w)$, không cộng lại gì cả vì "đỉnh" $w$ đại diện cho cạnh lên cha của nó, không thuộc đường đi.
• Truy vấn "gán giá trị" nhưng cập nhật như "cộng". Fenwick chỉ biết cộng; với set val[s] = x phải cộng hiệu $x-\text{val}[s]$ và nhớ cập nhật val[s]. Quên lưu val[s] thì lần gán thứ hai sai.
• Tràn số. Tổng cây con có thể tới $2·{10}^5·{10}^9=2·{10}^{14}$, cần long long cho Fenwick và biến kết quả.
• Rừng nhiều cây hoặc gốc không phải 1. Nếu đồ thị là rừng, chạy DFS từ mọi đỉnh chưa thăm và không reset timer, để các đoạn của những cây khác nhau không chồng lên nhau. Nếu đề cho gốc $r$ khác 1 thì phải gọi euler_tour(r): chương trình mẫu đang cố định euler_tour(1) (bản dạng $2n$ cũng bắt đầu từ đỉnh 1), và DFS từ sai gốc vẫn chạy êm nhưng mọi "cây con" đều sai.
• Hết bộ nhớ vì bảng nâng nhị phân. Với $N={10}^6$, bảng up có $20\times {10}^6$ số int (khoảng 80 MB); cộng các mảng khác, chương trình chính dùng khoảng 184 MB, sát giới hạn 256 MB thường gặp. Chỉ dựng bảng này khi thật sự cần LCA; bài chỉ hỏi cây con hoặc đường gốc thì bỏ hẳn.

Biến thể / Mở rộng

Segment tree trên mảng Euler

Khi thao tác trên cây con không phải "cộng" mà là gán, lật bit, lấy max..., thay Fenwick bằng Segment Tree (thường cần lan truyền lười). Ví dụ "đảo trạng thái mọi đèn trong cây con, đếm số đèn bật trong cây con" là segment tree lật bit trên đoạn $[\text{tin}[v],\text{tout}[v]]$. Một mẹo hay khác: gắn mốc thời gian cho thao tác. Chẳng hạn "đổ đầy cây con của $v$" là gán thời điểm cho cả đoạn của $v$, "tháo cạn $v$ và mọi tổ tiên" chỉ cần ghi thời điểm tại một điểm $\text{tin}[v]$; khi hỏi đỉnh $u$, nó còn nước khi và chỉ khi lần đổ gần nhất phủ $u$ muộn hơn mọi lần tháo có điểm nằm trong cây con của $u$ (một truy vấn max trên đoạn $[\text{tin}[u],\text{tout}[u]]$).

Truy vấn offline trên cây con

Câu hỏi "trong cây con của $u$ có bao nhiêu đỉnh có giá trị $\le k$" trở thành "trong đoạn $[\text{tin}[u],\text{tout}[u]]$ có bao nhiêu phần tử $\le k$": sắp truy vấn và phần tử theo $k$, thêm dần vào Fenwick theo vị trí (xem Xử lý truy vấn offline). Câu hỏi "trong cây con của $u$, các đỉnh có độ sâu $d$" thì gom các đỉnh cùng độ sâu vào một danh sách theo thứ tự $\text{tin}$ tăng dần; các đỉnh thuộc cây con $u$ là một đoạn liên tiếp của danh sách đó, tìm bằng hai lần tìm kiếm nhị phân.

Mo trên cây

Dạng $n$ phần tử biến truy vấn cây con thành truy vấn đoạn, áp thẳng thuật toán Mo. Với truy vấn đường đi $u$-$v$ dùng dạng $2n$ (giả sử $\text{tin}[u]\le \text{tin}[v]$): nếu $u$ là tổ tiên của $v$, đoạn là $[\text{tin}[u],\text{tin}[v]]$; ngược lại đoạn là $[\text{tout}[u],\text{tin}[v]]$ và phải thêm riêng $\text{lca}(u,v)$. Trong đoạn, đỉnh xuất hiện đúng một lần thuộc đường đi, đỉnh xuất hiện hai lần thì không, nên khi Mo thêm/bớt một vị trí ta bật/tắt đỉnh tương ứng.

Kết hợp với HLD, DSU on Tree, cây ảo

• HLD đánh số theo DFS ưu tiên con nặng trước. Đó vẫn là một thứ tự DFS, nên cây con của $u$ vẫn là đoạn $[\text{pos}[u],\text{pos}[u]+sz[u]-1]$. Một segment tree duy nhất vì vậy phục vụ được cả truy vấn đường đi (qua các chuỗi nặng) lẫn truy vấn cây con.
• DSU on Tree thường duyệt "mọi đỉnh trong cây con của con nhẹ" bằng vòng lặp for i in [tin[c], tout[c]]: order[i], không cần DFS lại. Ngược lại, khi bài có cập nhật xen kẽ thì DSU on Tree không dùng được, còn Euler tour + Fenwick/Segment Tree thì được.
• Cây ảo sắp các đỉnh quan trọng theo $\text{tin}$ và dùng phép kiểm tra tổ tiên $O(1)$ để dựng cây bằng ngăn xếp.

Quy hoạch động theo thứ tự DFS

Đánh số đỉnh theo $\text{tin}$ thì cây con của đỉnh ở vị trí $i$ là $[i,i+s{z}_i)$. Với các bài "chọn một tập đỉnh liên thông chứa gốc" (chọn đỉnh thì phải chọn cha), ta quy hoạch động trên dãy: ở vị trí $i$ hoặc chọn đỉnh đó và đi tiếp sang $i+1$, hoặc bỏ nó và nhảy qua cả cây con sang $i+s{z}_i$. Mỗi bước chỉ nhìn hai hàng kế tiếp, thay cho việc gộp các con như cái túi trên cây.

Đổi gốc khi hỏi cây con

Nếu truy vấn là "tổng cây con của $v$ khi gốc là $r$", không cần DFS lại. Vẫn giữ Euler tour với gốc 1 rồi xét ba trường hợp:

• $v=r$: cả cây.
• $v$ là tổ tiên thật sự của $r$ (theo gốc 1): gọi $c$ là con của $v$ nằm trên đường xuống $r$ (nhảy $r$ lên tới độ sâu $\text{dep}[v]+1$ bằng nâng nhị phân); cây con mới là cả cây trừ đoạn $[\text{tin}[c],\text{tout}[c]]$.
• Còn lại: cây con không đổi, vẫn là $[\text{tin}[v],\text{tout}[v]]$.

Bài tập luyện

Luyện kỹ thuật

• Truy vấn cây con (subqry) (Nâng cao) bài nhập môn: gán giá trị một đỉnh, hỏi tổng cây con; Fenwick "cập nhật điểm, tổng đoạn" trên mảng theo $\text{tin}$, đúng như truy vấn loại 1 và 2 ở trên.
• Truy vấn đường đi từ gốc (pathqry) (Nâng cao) cùng dữ liệu nhưng hỏi tổng đường gốc $\to s$ (trong đề là truy vấn 2 s): luyện chế độ ngược lại "cộng đoạn $[\text{tin},\text{tout}]$, hỏi điểm", hoặc dạng $2n$ với $+a$ lúc vào, $-a$ lúc ra.
• Truy vấn trên cây (treequery) (Kỳ cựu) thay mỗi đỉnh trong tập bằng cha của nó, rồi kiểm tra mọi đỉnh có nằm trên một đường gốc $\to u$: phép kiểm tra tổ tiên $O(1)$ bằng $\text{tin}/\text{tout}$ là trọng tâm.
• Số màu phân biệt trong cây con (distcolor) (Kỳ cựu) duỗi cây rồi đếm số giá trị phân biệt trên đoạn $[\text{tin}[u],\text{tout}[u]]$, giải được bằng Mo hoặc offline với Fenwick.
• Công tắc đèn cây con (subflip) (Kỳ cựu) đảo mọi đèn trong cây con và đếm đèn bật trong cây con: segment tree lật bit có lan truyền lười trên mảng Euler.

Muốn luyện thêm: Cây nước (watertree) (Kỳ cựu) "đổ đầy cây con" và "tháo cạn đường lên gốc" với $n,q\le 5·{10}^5$: mẹo mốc thời gian ở mục Biến thể, cộng thêm bắt buộc DFS không đệ quy.

Đề VOI

Trong các đề VOI hiện có trên CTOJ, Euler tour không phải toàn bộ lời giải của bài nào, nhưng là một mảnh ghép quan trọng ở hai bài sau:

• Canh tác lương thực (voi23_food) (Chuyên gia) VOI 2023: tập vùng được canh tác phải là một cây con liên thông chứa gốc. Đánh số các vùng theo thứ tự DFS để cây con là đoạn $[i,i+s{z}_i)$, rồi quy hoạch động trên dãy với lựa chọn "bỏ vùng $i$ thì nhảy qua cả cây con". Phần khó còn lại là tăng tốc bước chọn số thửa, không thuộc kỹ thuật này.
• Thu mua nông sản (voi24_fbuy) (Chuyên gia) VOI 2024: khi một làng đổi loại, cần tổng theo loại của một đại lượng trên các làng trong cây con của nó và trên các tổ tiên của nó. Phần cây con là Fenwick trên thứ tự DFS (lời giải chính thức dùng thứ tự HLD, vẫn là một thứ tự DFS), phần tổ tiên đi theo các chuỗi nặng của HLD.