Kỹ thuật đổi gốc (Rerooting)

Kỹ thuật đổi gốc (rerooting) giải lớp bài toán: tính một đại lượng quy hoạch động trên cây cho mọi đỉnh làm gốc. Ví dụ: tổng khoảng cách từ mỗi đỉnh tới mọi đỉnh khác, khoảng cách xa nhất từ mỗi đỉnh, số tập đỉnh liên thông chứa mỗi đỉnh. Cách ngây thơ chạy lại DFS từ từng gốc tốn $O(n^2)$; đổi gốc chỉ cần hai lượt duyệt cây và làm trong $O(n)$ (nhân thêm chi phí một phép gộp nếu phép gộp không phải $O(1)$).

Trang DP trên cây đã có một mục ngắn về đổi gốc với công thức tổng khoảng cách. Trang này đi sâu hơn: vì sao hai lượt là đủ, vì sao phải loại đóng góp của chính đỉnh con, cách xử lý khi phép gộp không có phép ngược (max, min, tích modulo), một khuôn mẫu tổng quát dùng lại được cho nhiều bài, và cách cài đặt không đệ quy cho $n$ lớn.

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

Cách ngây thơ và chỗ lãng phí

Giả sử ta đã biết giải bài toán khi cây có một gốc cố định: một DFS tính $dp[v]$ cho cây con của $v$ từ các $dp$ của con $v$. Muốn có đáp án cho mọi gốc, cách ngây thơ là lặp DFS đó $n$ lần: $O(n^2)$.

Nhưng khi đổi gốc từ $p$ sang một đỉnh kề $v$, hình dạng "cây có gốc" gần như không đổi. Chỉ một cạnh $p-v$ bị đảo chiều:

  gốc tại p                          gốc tại v

        p                                  v
      / | \                              / | \
     a  b  v          ===>              x  y  p
          / \                                / \
         x   y                              a   b

Các cây con của $a,b,x,y$ vẫn y nguyên. Chỉ có hai "cây con" thay đổi: cây con của $v$ (nay là cả cây) và cây con của $p$ (nay là cây bỏ đi phần của $v$). Vì vậy đáp án ở $v$ phải tính được từ đáp án ở $p$ bằng một lượng công việc nhỏ, không cần duyệt lại cả cây.

Hai lượt: down và up

Treo cây ở đỉnh $1$. Với mỗi đỉnh $v\ne 1$, gọi $p$ là cha của $v$. Cạnh $p-v$ chia cây thành hai phần:

• Phần dưới của $v$: cây con của $v$. Đặt $down[v]$ là giá trị DP của phần này, coi $v$ là gốc.
• Phần trên của $v$: mọi đỉnh còn lại, tức cây bỏ đi cây con của $v$. Đặt $up[v]$ là giá trị DP của phần này, coi $p$ là gốc.

            1
            |
           ...          <- phần trên của v: gốc tại p, KHÔNG chứa cây con của v
            |              (tổng hợp thành up[v])
            p
          / | \
       s1  s2  v        <- s1, s2: anh em của v
              / \
            c1   c2     <- phần dưới của v (down[v])

Khi $v$ làm gốc, các "nhánh" của $v$ chính là: cây con của từng con $c$ (đã có $down[c]$) và phần trên (có $up[v]$). Như vậy:

$$ans[v]=\text{gộp}(down[c_1],down[c_2],\dots ,up[v])$$

Và phần trên của một con $c$ của $v$ gồm: $v$, các anh em của $c$, và phần trên của $v$:

$$up[c]=\text{gộp}(\text{mọi }down[c^{\prime }]\text{ với }{c}^{\prime }\text{ là con khác }c\text{ của }v,up[v])$$

Từ đó có thứ tự tính rõ ràng:

1. Lượt xuống (từ lá lên gốc): $down[v]$ cần $down$ của các con, nên duyệt con trước cha. Đây chính là DP trên cây quen thuộc.
2. Lượt lên (từ gốc xuống lá): $up[c]$ cần $up[v]$ của cha và $down$ của anh em (đã có từ lượt 1), nên duyệt cha trước con. Đỉnh gốc không có phần trên.

Tên gọi hơi ngược nhưng dễ nhớ: $down$ nhìn xuống cây con, $up$ nhìn lên phía cha. Thông tin của $up$ chảy từ gốc xuống lá.

Vì sao phải loại đóng góp của chính $v$

$up[c]$ mô tả phần cây không chứa cây con của $c$. Nếu vô tình gộp cả $down[c]$ vào $up[c]$, ta đếm cây con của $c$ hai lần: một lần ở phần dưới, một lần "vòng lên cha rồi đi xuống lại chính mình". Với bài đỉnh xa nhất, điều đó tương ứng với một "đường đi" $c\to v\to c\to \dots$ đi lại một cạnh hai lần, không phải đường đi đơn trên cây, và cho kết quả lớn giả (xem ví dụ chạy tay bên dưới).

Nói cách khác: đứng ở $v$, với mỗi con $c$ ta cần gộp của tất cả nhánh trừ đúng một nhánh. Đây là câu hỏi cốt lõi của kỹ thuật.

Gộp "tất cả trừ một": khi nào trừ được, khi nào không

Giả sử $v$ có $k$ nhánh với giá trị (đã qua cạnh) $x_1,x_2,\dots ,x_k$, và phép gộp là $\oplus$.

• Phép gộp có phép ngược (cộng, XOR, nhân với số khác $0$ modulo nguyên tố): tính tổng $X=x_1\oplus \dots \oplus x_k$ một lần rồi "bỏ" $x_i$ bằng phép ngược. Với tổng khoảng cách, đó là phép trừ, và ta được công thức gọn $ans[v]=ans[p]+n-2sz[v]$.
• Phép gộp không có phép ngược (max, min, gcd, tích modulo có thể bằng $0$): không "trừ" được. Ví dụ $max(5,3,5)$ bỏ đi một số $5$ vẫn là $5$, còn $max(5,3)$ bỏ đi $5$ là $3$: chỉ biết giá trị max thì không suy ra được.

Với trường hợp thứ hai, dùng tiền tố / hậu tố:

$$pr{e}_i=x_1\oplus \dots \oplus x_i,su{f}_i=x_i\oplus \dots \oplus x_k$$

$$\text{tất cả trừ }{x}_i=pr{e}_{i-1}\oplus su{f}_{i+1}$$

Chỉ cần $\oplus$ kết hợp (associative) và có phần tử trung hòa (identity) để làm $pr{e}_0$, $su{f}_{k+1}$. Không cần giao hoán, không cần phép ngược. Mỗi đỉnh tốn $O(k)$ phép gộp, tổng trên cả cây là $O(\sum \mathrm{deg})=O(n)$.

Với max/min còn một mẹo rẻ hơn: giữ hai giá trị tốt nhất và con đạt giá trị tốt nhất. Bỏ đi con $c$: nếu $c$ là con tốt nhất thì dùng giá trị tốt nhì, ngược lại dùng giá trị tốt nhất. Mẹo này dựa vào tính chất riêng của max/min (kết quả gộp luôn bằng một trong các phần tử, nên bỏ một phần tử thì đáp án chỉ có thể là tốt nhất hoặc tốt nhì); nó cho cùng kết quả với tiền tố/hậu tố nhưng rẻ hơn về bộ nhớ, và không áp dụng được cho phép gộp tổng quát như gcd hay tích.

Khuôn mẫu: merge, add_edge, finalize

Rất nhiều bài đổi gốc có chung cấu trúc. Tách DP trên cây thành ba thao tác:

Khi đó $dp[v]=\mathtt{\text{finalize}}({⨁}_c\mathtt{\text{add\_edge}}(dp[c]),v)$, và đổi gốc chỉ là: tại mỗi đỉnh, danh sách nhánh gồm các con và phần trên; đáp án là gộp tất cả, còn $up$ của từng con là gộp tất cả trừ con đó. Ba bài kinh điển viết theo khuôn mẫu:

Giải thích dòng cuối: một tập liên thông chứa gốc $v$, với mỗi con $c$, hoặc không lấy gì trong cây con của $c$ (1 cách), hoặc lấy một tập liên thông chứa $c$ ($dp[c]$ cách). Các con độc lập nên nhân lại: $dp[v]=\prod (dp[c]+1)$.

Ví dụ chạy tay

Dùng chung một cây 5 đỉnh, treo ở đỉnh $1$:

        1
       / \
      2   3
         / \
        4   5

Tổng khoảng cách: đổi gốc bằng phép trừ

Lượt xuống. $sz[v]$ là số đỉnh cây con, $down[v]$ là tổng khoảng cách từ $v$ tới các đỉnh trong cây con. Đi qua cạnh $v\to c$, mọi đỉnh trong cây con $c$ xa thêm $1$, nên $down[v]={\sum }_c(down[c]+sz[c])$.

Lượt lên. Tại gốc, $ans[1]=down[1]=6$. Dời gốc từ $p$ sang con $v$: $sz[v]$ đỉnh trong cây con $v$ gần thêm $1$, còn $n-sz[v]$ đỉnh kia xa thêm $1$:

$$ans[v]=ans[p]-sz[v]+(n-sz[v])=ans[p]+n-2sz[v]$$

ans[1] = 6
ans[2] = ans[1] + 5 - 2*1 = 9
ans[3] = ans[1] + 5 - 2*3 = 5
ans[4] = ans[3] + 5 - 2*1 = 8
ans[5] = ans[3] + 5 - 2*1 = 8

Kiểm tra $ans[3]$: khoảng cách từ $3$ tới $1,2,4,5$ là $1,2,1,1$, tổng $5$. Ở đây ta không cần tính $up$ tường minh vì phép cộng có phép trừ: "tất cả trừ cây con $v$" chính là $ans[p]$ trừ đi phần của $v$.

Đỉnh xa nhất: $up$ tường minh và lỗi quên loại chính mình

Đặt $down[v]$ = độ sâu lớn nhất trong cây con $v$ (tính từ $v$), $up[v]$ = đường đi dài nhất xuất phát từ $v$ mà cạnh đầu tiên đi lên cha. Đáp án $ans[v]=max(down[v],up[v])$ và

$$up[v]=1+max(up[p],{max}_{s\text{ là anh em của }v}(down[s]+1\left)\right)$$

với quy ước $up[\text{gốc}]=0$ (đứng ở gốc, "phần trên" rỗng, đi được $0$ cạnh).

Lưu ý về quy ước. Riêng mục này và đoạn code "Khoảng cách xa nhất từ mỗi đỉnh" bên dưới dùng quy ước $up[v]$ đã đi qua cạnh $p-v$ (số hạng $1+$ ở đầu công thức), vì như vậy $ans[v]=max(down[v],up[v])$ gọn hơn. Khuôn mẫu tổng quát và lỗi "Nhầm vai trò của $up[v]$" ở phần sau dùng quy ước chưa qua cạnh ($up[v]$ là DP gốc tại $p$, cạnh $p-v$ được cộng bằng add_edge khi dùng ở $v$). Hai quy ước đều đúng, không mâu thuẫn; điều quan trọng là chọn một và cộng cạnh $p-v$ đúng một lần.

Lượt xuống: $down[4]=down[5]=down[2]=0$, $down[3]=1$, $down[1]=2$. Tại mỗi đỉnh giữ hai giá trị $down[c]+1$ lớn nhất:

Lượt lên (từ gốc xuống):

up[2] = 1 + max(up[1]=0, anh em tốt nhất của 2 = 2 (con 3))       = 3
up[3] = 1 + max(up[1]=0, anh em tốt nhất của 3: con 3 là tốt nhất,
                         nên lấy tốt nhì = 1 (con 2))              = 2
up[4] = 1 + max(up[3]=2, tốt nhì của 3 = 1)                         = 3
up[5] = 1 + max(up[3]=2, tốt nhất của 3 = 1 (con 4))                = 3

Nếu quên loại chính mình và luôn lấy "tốt nhất" của cha: $up[3]=1+max(0,2)=3$, suy ra $ans[3]=3$. Sai, vì giá trị $2$ đó đến từ chính nhánh của $3$: "đường đi" $3\to 1\to 3\to 4$ đi lại cạnh $1-3$. Đáp án đúng là $2$.

Tiền tố / hậu tố tại một đỉnh: đếm tập liên thông

Bài: với mỗi đỉnh $v$, đếm số tập đỉnh liên thông chứa $v$. Dùng khuôn mẫu dòng cuối của bảng trên: $dp[v]={\prod }_c(dp[c]+1)$.

Lượt xuống: $down[4]=down[5]=down[2]=1$, $down[3]=2·2=4$, $down[1]=2·5=10$.

Tại đỉnh 1 (gốc, chỉ có hai nhánh là con $2$ và con $3$):

nhánh i      :   1 (con 2)   2 (con 3)
x_i = down+1 :      2           5
pre          :  1   2          10          (pre_0 = 1 là phần tử trung hòa)
suf          :     10           5    1     (suf_3 = 1)

ans[1] = pre_2           = 10
up[2]  = pre_0 * suf_2   = 1 * 5 = 5     (tập liên thông chứa 1, không dùng đỉnh 2)
up[3]  = pre_1 * suf_3   = 2 * 1 = 2     (chỉ {1} và {1, 2})

Tại đỉnh 3 (ba nhánh: phần trên qua cha $1$, con $4$, con $5$):

nhánh i      :  1 (cha, up[3])  2 (con 4)  3 (con 5)
x_i          :       2 + 1 = 3       2          2
pre          :  1    3               6         12
suf          :      12               4          2    1

ans[3] = pre_3         = 12
up[4]  = pre_1 * suf_3 = 3 * 2 = 6
up[5]  = pre_2 * suf_4 = 6 * 1 = 6

Tiếp tục: $ans[2]=up[2]+1=6$, $ans[4]=up[4]+1=7$, $ans[5]=7$. Kết quả $10,6,12,7,7$ khớp với vét cạn. Trong bài này nếu đáp án lấy modulo $p$ và một $x_i\equiv 0\left(\mathrm{mod}p\right)$, cách "chia cho $x_i$" sẽ hỏng, còn tiền tố/hậu tố thì không bị ảnh hưởng.

Cài đặt

Duyệt không đệ quy bằng thứ tự BFS

Với cây đường thẳng $n=2·{10}^5$, DFS đệ quy sâu $2·{10}^5$ tầng và dễ tràn stack. Đổi gốc không cần thứ tự DFS thật sự, chỉ cần:

• lượt xuống: con trước cha;
• lượt lên: cha trước con.

Thứ tự BFS từ gốc thỏa "cha trước con", đảo ngược lại thì thỏa "con trước cha". Vì thế mọi chương trình dưới đây đều lấy thứ tự BFS một lần rồi duyệt xuôi, ngược bằng vòng for, không đệ quy.

Tổng khoảng cách tới mọi đỉnh (C++)

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

int main() {
    int n;
    scanf("%d", &n);
    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);
    }

    // BFS order from root 1: parents always appear before children
    vector<int> order, par(n + 1, 0);
    order.reserve(n);
    order.push_back(1);
    par[1] = -1;
    for (int i = 0; i < (int)order.size(); i++) {
        int u = order[i];
        for (int v : adj[u])
            if (v != par[u]) { par[v] = u; order.push_back(v); }
    }

    vector<long long> sz(n + 1, 1), down(n + 1, 0), ans(n + 1, 0);
    // Pass 1 (bottom-up): reverse BFS order = children before parent
    for (int i = n - 1; i >= 1; i--) {
        int v = order[i], p = par[v];
        sz[p] += sz[v];
        down[p] += down[v] + sz[v];   // every vertex below v gets 1 edge farther
    }
    // Pass 2 (top-down): move the root across edge p - v
    ans[1] = down[1];
    for (int i = 1; i < n; i++) {
        int v = order[i], p = par[v];
        ans[v] = ans[p] + n - 2 * sz[v];  // sz[v] vertices get closer, n - sz[v] get farther
    }
    for (int v = 1; v <= n; v++) printf("%lld%c", ans[v], v == n ? '\n' : ' ');
}

Tổng khoảng cách (Python)

Python cũng nên tránh đệ quy: giới hạn đệ quy mặc định chỉ khoảng $1000$ tầng.

import sys

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

    # BFS order instead of recursion (no recursion limit issues)
    par = [0] * (n + 1)
    par[1] = -1
    order = [1]
    for u in order:
        for v in adj[u]:
            if v != par[u]:
                par[v] = u
                order.append(v)

    sz = [1] * (n + 1)
    down = [0] * (n + 1)
    for v in reversed(order[1:]):
        p = par[v]
        sz[p] += sz[v]
        down[p] += down[v] + sz[v]

    ans = [0] * (n + 1)
    ans[1] = down[1]
    for v in order[1:]:
        ans[v] = ans[par[v]] + n - 2 * sz[v]
    sys.stdout.write(" ".join(map(str, ans[1:])) + "\n")

main()

Khoảng cách xa nhất từ mỗi đỉnh: giữ hai giá trị tốt nhất

Code này dùng quy ước $up[v]$ đã đi qua cạnh cha $p-v$, giống ví dụ chạy tay ở trên.

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

int main() {
    int n;
    scanf("%d", &n);
    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);
    }
    vector<int> order, par(n + 1, 0);
    order.push_back(1);
    par[1] = -1;
    for (int i = 0; i < (int)order.size(); i++) {
        int u = order[i];
        for (int v : adj[u])
            if (v != par[u]) { par[v] = u; order.push_back(v); }
    }

    // best1[u], best2[u]: two largest values of down[c] + 1 over children c
    // who1[u]: the child that gives best1[u]
    vector<int> best1(n + 1, 0), best2(n + 1, 0), who1(n + 1, 0), up(n + 1, 0);
    for (int i = n - 1; i >= 1; i--) {
        int v = order[i], p = par[v];
        int cand = best1[v] + 1;          // best1[v] == down[v]
        if (cand > best1[p]) { best2[p] = best1[p]; best1[p] = cand; who1[p] = v; }
        else if (cand > best2[p]) best2[p] = cand;
    }
    // up[v]: longest path starting at v whose first edge goes to the parent
    up[1] = 0;
    for (int i = 1; i < n; i++) {
        int v = order[i], p = par[v];
        int sibling = (who1[p] == v) ? best2[p] : best1[p];  // exclude v itself
        up[v] = 1 + max(up[p], sibling);
    }
    for (int v = 1; v <= n; v++)
        printf("%d%c", max(best1[v], up[v]), v == n ? '\n' : ' ');
}

Lưu ý dòng who1[p] == v: so sánh theo chỉ số con, không so theo giá trị. Nếu hai con cùng đạt giá trị tốt nhất thì best2[p] cũng bằng giá trị đó, nên kết quả vẫn đúng.

Khuôn mẫu tổng quát với tiền tố / hậu tố

Chỉ phần đầu (giữa hai dòng comment Problem-specific) thay đổi theo bài. Ví dụ dưới đây đếm số tập đỉnh liên thông chứa mỗi đỉnh, modulo ${10}^9+7$. Muốn đổi sang bài khác, thay bốn định nghĩa theo bảng ở mục Ý tưởng.

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

// ---- Problem-specific part: count connected vertex sets containing the root
// dp[v] = prod over children (dp[c] + 1)
const long long MOD = 1'000'000'007LL;
using T = long long;                                   // DP value of a rooted subtree
using A = long long;                                   // accumulator (monoid element)
const A IDENTITY = 1;                                  // neutral element of merge
A merge(A x, A y) { return x * y % MOD; }              // associative combine
A add_edge(T child) { return (child + 1) % MOD; }      // child subtree hung under an edge
T finalize(A acc, int /*v*/) { return acc; }           // add the vertex itself
// ---- End of problem-specific part

int main() {
    int n;
    scanf("%d", &n);
    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);
    }
    vector<int> order, par(n + 1, 0);
    order.push_back(1);
    par[1] = 0;
    for (int i = 0; i < (int)order.size(); i++) {
        int u = order[i];
        for (int v : adj[u])
            if (v != par[u]) { par[v] = u; order.push_back(v); }
    }

    // Pass 1: down[v] = DP of the subtree of v (rooted at 1)
    vector<T> down(n + 1), up(n + 1), ans(n + 1);
    for (int i = n - 1; i >= 0; i--) {
        int v = order[i];
        A acc = IDENTITY;
        for (int c : adj[v]) if (c != par[v]) acc = merge(acc, add_edge(down[c]));
        down[v] = finalize(acc, v);
    }

    // Pass 2: up[v] = DP of the "rest of the tree" rooted at par[v], v's subtree removed
    vector<A> contrib, pre, suf;
    for (int u : order) {
        const vector<int>& nb = adj[u];
        int k = nb.size();
        contrib.assign(k, IDENTITY);
        for (int i = 0; i < k; i++)
            contrib[i] = (nb[i] == par[u]) ? add_edge(up[u]) : add_edge(down[nb[i]]);
        pre.assign(k + 1, IDENTITY);
        suf.assign(k + 1, IDENTITY);
        for (int i = 0; i < k; i++) pre[i + 1] = merge(pre[i], contrib[i]);
        for (int i = k - 1; i >= 0; i--) suf[i] = merge(contrib[i], suf[i + 1]);

        ans[u] = finalize(pre[k], u);                  // all neighbours are children now
        for (int i = 0; i < k; i++) {
            int c = nb[i];
            if (c == par[u]) continue;
            up[c] = finalize(merge(pre[i], suf[i + 1]), u);   // everything except c
        }
    }
    for (int v = 1; v <= n; v++) printf("%lld%c", ans[v], v == n ? '\n' : ' ');
}

Hai điểm tinh tế trong khuôn mẫu:

• $up[c]$ được lưu dưới dạng giá trị DP (đã finalize tại $u$), không phải đóng góp. Khi dùng ở đỉnh $c$, nó lại đi qua add_edge như mọi nhánh khác. Nhờ vậy phần trên và các cây con được đối xử hoàn toàn đối xứng.
• Tại gốc, par[1] = 0 không trùng đỉnh nào, nên danh sách nhánh của gốc chỉ gồm các con, đúng như mong muốn.

Để dùng cho tổng khoảng cách, thay phần đầu bằng kiểu cặp:

struct P { long long sum, cnt; };
using T = P; using A = P;
const A IDENTITY = {0, 0};
A merge(A x, A y) { return {x.sum + y.sum, x.cnt + y.cnt}; }
A add_edge(T c) { return {c.sum + c.cnt, c.cnt}; }     // every vertex gets 1 edge farther
T finalize(A acc, int) { return {acc.sum, acc.cnt + 1}; } // the root itself: distance 0

và in ans[v].sum. Cả ba biến thể (xa nhất, tổng khoảng cách, tập liên thông) đã được đối chiếu với vét cạn trên cây ngẫu nhiên nhỏ.

Độ phức tạp

• Thời gian $O(n)$. Lấy thứ tự BFS mất $O(n)$. Lượt xuống duyệt mỗi cạnh một lần. Ở lượt lên, đỉnh $u$ bậc $\mathrm{deg}(u)$ tốn $O(\mathrm{deg}(u))$ cho mảng đóng góp, tiền tố, hậu tố và cho các con; tổng ${\sum }_u\mathrm{deg}(u)=2(n-1)$. Nếu mỗi merge tốn $O(M)$ (ví dụ gộp mảng độ dài $M$) thì tổng là $O(nM)$.
• Bộ nhớ $O(n)$. Danh sách kề $2(n-1)$ phần tử, các mảng $down$, $up$, $ans$, $par$, $order$ cỡ $n$. Các mảng pre, suf dùng lại giữa các đỉnh, lớn nhất bằng bậc lớn nhất $\le n$. Không có stack đệ quy.
• So với cách ngây thơ: $n$ lần DFS là $O(n^2)$, với $n=2·{10}^5$ là $4·{10}^{10}$ phép tính, không thể chạy kịp.

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

• Không loại đóng góp của chính con khi tính $up$. Triệu chứng: đáp án lớn hơn đúng (bài max) hoặc đếm trùng (bài tổng, bài đếm) ở những đỉnh là "con tốt nhất" của cha. Cách tránh: mọi $up[c]$ phải là gộp của tất cả nhánh của cha trừ nhánh $c$; kiểm tra lại trên ví dụ nhỏ như cây 5 đỉnh ở trên.
• Dùng phép chia modulo để "bỏ" một nhánh. Với tích modulo, $dp[c]+1$ có thể chia hết cho $p$ (với $n$ lớn điều này hoàn toàn có thể xảy ra, và đề dạng này thường có test bẫy). Khi đó không tồn tại nghịch đảo và chia sẽ cho kết quả rác. Cách tránh: dùng tiền tố/hậu tố, hoặc lưu riêng số thừa số bằng $0$ cùng tích các thừa số khác $0$.
• Trừ với max/min. Không thể "bỏ" một phần tử khỏi max bằng phép trừ. Dùng hai giá trị tốt nhất kèm chỉ số con, hoặc tiền tố/hậu tố.
• Cập nhật hai giá trị tốt nhất sai. Các biến thể sai hay gặp: chỉ lưu best1 mà không lưu best2 (con tốt nhất không có giá trị thay thế); khi cand > best1[p] thì gán best1 mới nhưng quên dời best1 cũ xuống best2; hoặc chỉ cập nhật best2 khi cand < best1[p] (bỏ sót trường hợp hai con bằng nhau, làm best2 nhỏ hơn thực tế). Lời khuyên: cập nhật đúng khuôn if (cand > best1) {...} else if (cand > best2) {...} như code trên, và lưu who1[p] để so who1[p] == v theo chỉ số. So theo giá trị (down[v] + 1 == best1[p] thì dùng best2) cũng cho đáp án đúng khi best2 được cập nhật đầy đủ, nhưng so theo chỉ số dễ kiểm tra hơn và vẫn đúng khi mở rộng sang giữ thêm thông tin kèm theo con.
• Tính lại "tất cả trừ một" bằng vòng lặp qua mọi anh em. Trông như $O(n)$ nhưng thực chất là $O(\sum {\mathrm{deg}}^2)$: cây hình sao $n=2·{10}^5$ cho $4·{10}^{10}$ phép tính, TLE. Phải dùng tiền tố/hậu tố hoặc phép ngược.
• Tràn stack với DFS đệ quy. Cây đường thẳng $n=2·{10}^5$ làm hai lượt đệ quy sâu $2·{10}^5$ tầng; nhiều máy chấm chỉ có stack vài MB, bị RTE khó đoán. Dùng thứ tự BFS như trên.
• Tràn số int. Tổng khoảng cách trên cây đường thẳng $n=2·{10}^5$ tới khoảng $2·{10}^{10}$. Khai báo long long cho $down$, $ans$, và cẩn thận biểu thức n - 2 * sz[v] khi sz là int (kết quả thì nhỏ, nhưng các phép cộng vào ans phải là long long).
• Chọn sai phần tử trung hòa. Với max của các giá trị có thể âm, IDENTITY phải là $-\infty$ chứ không phải $0$; nếu không, một đỉnh lá hoặc gốc không có phần trên sẽ nhận giá trị $0$ giả. Tương tự, với tích thì trung hòa là $1$, với tổng là $0$.
• Nhầm vai trò của $up[v]$. Trong khuôn mẫu tổng quát, $up[v]$ là DP của phần trên gốc tại cha $p$, chưa đi qua cạnh $p-v$. Nếu ở chỗ này đã cộng cạnh, rồi đến $v$ lại add_edge thêm lần nữa, sẽ lệch một cạnh (off-by-one) ở mọi đỉnh trừ gốc. (Mục đỉnh xa nhất dùng quy ước ngược lại, $up[v]$ đã qua cạnh, nên ở đó $ans[v]=max(down[v],up[v])$ không cộng thêm gì. Dùng quy ước nào cũng được, miễn cạnh $p-v$ được cộng đúng một lần.)
• Quên trường hợp $n=1$. Không có cạnh nào; các vòng for (int i = 1; i < n; i++) không chạy, đáp án của đỉnh duy nhất phải là giá trị của cây một đỉnh ($0$ khoảng cách, $1$ tập liên thông...).

Biến thể / Mở rộng

• Cạnh có trọng số. Cho add_edge nhận thêm trọng số cạnh: add_edge(t, w). Với tổng khoảng cách có trọng số: $(sum+w·cnt,cnt)$; với đỉnh xa nhất: $t+w$. Nhớ lưu trọng số cạnh cha của mỗi đỉnh để dùng lại ở lượt lên.
• Tổng có trọng số đỉnh. Bài "chi phí lớn nhất" thay $cnt$ bằng tổng trọng số đỉnh trong cây con, công thức chuyển gốc thành $ans[v]=ans[p]+(S-W_v)-W_v$ với $S$ là tổng toàn cây, $W_v$ là tổng trong cây con $v$.
• Moment bậc cao. Tổng bình phương khoảng cách: giữ bộ ba $(cnt,\sum d,\sum d^2)$ vì $(d+1{)}^2=d^2+2d+1$. Tổng quát, $\sum d^k$ cần các moment bậc $0..k$.
• Đáp án theo cạnh. Nhiều bài hỏi "cắt cạnh $p-v$ thì hai nửa ra sao": đó chính là cặp $(down[v],up[v])$, không cần gì thêm.
• Đổi gốc cho DP dạng mảng. Nếu $dp[v]$ là một mảng (ví dụ số đỉnh ở mỗi khoảng cách $\le K$), merge tốn $O(K)$ và tổng là $O(nK)$. Với DP cái túi mà mảng dài bằng kích thước cây con (xem Knapsack trên cây), đổi gốc thường không còn rẻ, vì phần trên có kích thước gần $n$ ở mọi đỉnh.
• Khi đổi gốc không đủ. Nếu đại lượng phụ thuộc cả hai đầu đường đi theo kiểu không tách được (ví dụ trọng số nhỏ nhất trên đường nhân với bình phương độ dài), thường phải chuyển sang phân rã centroid.
• Đổi gốc cho truy vấn cây con. Khi gốc thay đổi theo truy vấn và cần tổng trên "cây con" theo gốc mới, dùng Euler tour kèm LCA hoặc binary lifting để tìm con của đỉnh về phía gốc mới, rồi lấy phần bù trên mảng Euler. Đó là bài toán khác: ở đây ta cần đáp án cho mọi gốc cùng lúc, còn ở đó mỗi truy vấn một gốc.
• Nền tảng. Nếu chưa quen DP một gốc cố định (tập độc lập, đường kính, ghép cặp), đọc DP trên cây trước.

Bài tập luyện

Luyện kỹ thuật

Danh sách xếp theo độ khó trên hệ thống. Nếu mới làm quen đổi gốc, nên làm treedist2 trước treedist1: công thức phép trừ của treedist2 đơn giản hơn, dù rating của nó cao hơn một chút.

• Khoảng cách xa nhất từ mỗi đỉnh (treedist1) (Nâng cao) phép gộp là max nên không trừ được: luyện cách giữ hai giá trị tốt nhất kèm chỉ số con để tính $up$.
• Tổng khoảng cách từ mỗi đỉnh (treedist2) (Nâng cao) đổi gốc bằng phép trừ, cách tiếp cận dễ nhất để bắt đầu: $ans[v]=ans[p]+n-2sz[v]$, chú ý long long.
• Cây có chi phí lớn nhất (treecost) (Kỳ cựu) tổng khoảng cách có trọng số đỉnh: thay kích thước cây con bằng tổng trọng số cây con trong công thức chuyển gốc, rồi lấy max trên mọi đỉnh.
• Sinh Cây Ngẫu Nhiên (randtree) (Kỳ cựu) đưa xác suất về tổng theo mọi gốc $r$ của ${\prod }_{v}1/s{z}_r(v)$, rồi chia cho $(N-1)!$; khi dời gốc qua một cạnh chỉ hai kích thước thay đổi, nên đổi gốc với tích modulo và nghịch đảo (ở đây kích thước luôn khác $0$ nên chia được).
• Nâng cấp đường (roadimp) (Chuyên gia) $dp[v]=\prod (dp[c]+1)$ cho mọi thủ đô; $dp[c]+1$ có thể chia hết cho ${10}^9+7$ nên bắt buộc dùng tiền tố/hậu tố thay cho nghịch đảo.

Đề VOI

Trong kho đề VOI hiện có, chưa có bài nào mà lời giải đầy đủ dựa trên đổi gốc. Bài dưới đây dùng đổi gốc cho một phần các subtask.

• Mạng truyền tin (voi24_netw) (Kỳ cựu) VOI 2024: cần một đại lượng cho mọi máy chủ $r$, nhưng lời giải đầy đủ dùng phân rã centroid. Đổi gốc là chìa khóa cho các subtask trung gian: khi mọi $w_i=1$, hãy nghĩ xem mỗi cây con cần giữ những tổng nào để dời gốc qua một cạnh mà vẫn cập nhật được tổng bình phương khoảng cách; khi $w_i$ nhỏ, thử tách $C_{min}$ thành tổng theo các ngưỡng trọng số.