HDU 4916 Count on the path：樹上路徑外最小標號查詢

HDU 4916 Count on the path：樹上路徑外最小標號查詢

題目大意：給定一棵 n 節點樹（n ≤ 1,000,000），m 次詢問。每次詢問給出 u, v，求不在 u-v 路徑上的節點的最小標號。強制在線：詢問參數需與上一答案異或。

核心觀察

若 u, v 的 LCA 不為 1，則節點 1 必不在路徑上，答案直接為 1。但求 LCA 會超時。
替代方案：以節點 1 為根 DFS，給每個節點染色，顏色為其所屬的 1 的直接子樹編號。若兩節點顏色相同，說明它們在同一子樹內，LCA 不為 1；否則 LCA 為 1，答案為 1。

染色與預處理

• dfs1：計算每個節點子樹內的最小標號 f[u][0..3]（保存最小的 4 個值，便於排除路徑上節點）。
• dfs2：計算每個節點向上（非子樹方向）的最小標號 g[u]。

查詢邏輯

if (col[u] == col[v]) { // 同子樹
    if (u == 1 || v == 1) ans = 2;
    else ans = 1;
} else { // 不同子樹，LCA=1
    ans = min(f[v][0], min(g[u], g[v]));
    if (u != 1) {
        ans = min(ans, f[u][0]);
        int cv = min(col[v], f[col[v]][0]);
        int cu = min(col[u], f[col[u]][0]);
        for (int j = 0; j < 3; j++)
            if (f[1][j] != cu && f[1][j] != cv) { ans = min(ans, f[1][j]); break; }
    } else {
        int cv = min(col[v], f[col[v]][0]);
        for (int j = 0; j < 3; j++)
            if (f[1][j] != cv) { ans = min(ans, f[1][j]); break; }
    }
}

複雜度

• 預處理 O(n)，單次查詢 O(1)，總 O(n + m)。
• 記憶體：f[N][4], g[N], col[N] 等，約 40MB，符合限制。