Codeforces 429A Xor-tree：樹上奇偶層翻轉貪心 DFS

題目大意

給定 n ≤ 10^5 節點的樹（根為 1），每節點初始值 init[i] ∈ {0,1}，目標值 goal[i] ∈ {0,1}。
操作：選節點 x，翻轉 x、x 的孫子節點、曾孫節點的孫子……即**與 x 深度同奇偶性**的子樹節點。
求最少操作次數及操作節點列表。

核心觀察

• 操作影響「同深度奇偶性」的後代。根深度 0（偶）。
• 自頂向下 DFS，維護兩個翻轉標記：flipEven（偶數層累積翻轉次數模 2）、flipOdd（奇數層）。
• 當前節點 u 實際值 = init[u] ^ (depth%2==0 ? flipEven : flipOdd)。
• 若實際值 ≠ goal[u]，**必須在 u 操作**（因為祖先操作已定，子孫操作不影響 u）。操作後翻轉對應奇偶標記。
• 貪心最優：首次發現不匹配即操作，延遲只會增加操作數。

DFS 遞歸邏輯

void dfs(int u, int parent, int flipEven, int flipOdd) {
    int curVal = init[u] ^ ((depth[u] & 1) ? flipOdd : flipEven);
    if (curVal != goal[u]) {
        ans.push_back(u);
        if (depth[u] & 1) flipOdd ^= 1;
        else flipEven ^= 1;
    }
    for (int v : g[u]) if (v != parent)
        dfs(v, u, flipEven, flipOdd);
}

完整代碼

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

const int MAXN = 100005;
int n, init[MAXN], goal[MAXN], depth[MAXN];
vector<int> g[MAXN], ans;

void dfs(int u, int p, int flipEven, int flipOdd) {
    int cur = init[u] ^ ((depth[u] & 1) ? flipOdd : flipEven);
    if (cur != goal[u]) {
        ans.push_back(u);
        if (depth[u] & 1) flipOdd ^= 1;
        else flipEven ^= 1;
    }
    for (int v : g[u]) if (v != p) {
        depth[v] = depth[u] + 1;
        dfs(v, u, flipEven, flipOdd);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    for (int i = 1; i < n; ++i) {
        int u, v; cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    for (int i = 1; i <= n; ++i) cin >> init[i];
    for (int i = 1; i <= n; ++i) cin >> goal[i];
    depth[1] = 0;
    dfs(1, 0, 0, 0);
    cout << ans.size() << "\n";
    for (int x : ans) cout << x << "\n";
    return 0;
}

複雜度

• 時間 O(n)，單次 DFS。
• 空間 O(n)，鄰接表 + 遞歸棧（深度 ≤ n，建議改迭代或加 pragma 擴棧）。

關鍵點總結

總結

CF 429A Xor-tree 是「樹上奇偶層獨立翻轉」的經典模型。關鍵在於識別操作的影響範圍僅限於同深度奇偶性的子樹，從而將問題轉化為兩條獨立的前綴翻轉鏈，用 DFS 傳遞兩個狀態變量即可貪心構造最優解。此類「樹上操作影響特定深度/層級」問題（如 Codeforces 274B, 748C）均可用相似「按深度分組 + 狀態傳遞」思路解決。