Codeforces 216C Valera and Elections：樹上 DFS 贪心選點

題目連結：Codeforces Round #216 C。給定一棵 N ≤ 10^5 節點的樹（根為 1），部分邊標記為需修復 (權值 2) 或不需 (權值 1)。選擇一組節點，使得從這些節點到根的路徑覆蓋所有需修復邊，且集合大小最小。輸出任意最小集合 (SPJ)。

核心觀察

• 從根 DFS，回溯時決定是否將當前節點加入答案集合。
• 若某節點到父節點的邊需修復 (權值 2)，必須在該節點或其子樹中選點。
• 若子樹已有節點被選中（即已覆蓋該邊），則當前節點無需再選。

演算法流程

1. 建立無向圖鄰接表，邊存儲目標節點、權值、下一條邊索引。
2. 從根節點 1 開始 DFS，標記訪問。
3. 遞歸處理所有子節點，累計子樹「已選點數」sum[u]。
4. 回溯判斷：
   • 若當前邊權值為 2 或 sum[u] ≥ 1 (子樹已有選點) → 當前路徑已被覆蓋。
   • 若上述條件成立且 sum[u] == 0 (子樹無選點) → 必須選當前節點，加入答案，返回 1 向上傳遞「已覆蓋」。
   • 否則返回 0 (無需覆蓋)。

代碼實現 (C)

#include 
#include 
#include 

#define MAXN 101000

struct Edge { int to, w, next; } e[MAXN << 2];
int head[MAXN], ecnt;
int vis[MAXN], sum[MAXN], ans[MAXN], ancnt;

void add_edge(int u, int v, int w) {
    e[ecnt] = (struct Edge){v, w, head[u]};
    head[u] = ecnt++;
}

int dfs(int u, int w) {
    vis[u] = 1;
    for (int i = head[u]; ~i; i = e[i].next) {
        int v = e[i].to;
        if (vis[v]) continue;
        sum[u] += dfs(v, e[i].w);
    }
    if (w == 2 || sum[u] >= 1) {
        if (sum[u] == 0) ans[ancnt++] = u;
        return 1;
    }
    return 0;
}

int main() {
    int n;
    while (scanf("%d", &n) == 1) {
        ecnt = ancnt = 0;
        memset(head, -1, sizeof(head));
        memset(sum, 0, sizeof(sum));
        memset(vis, 0, sizeof(vis));
        for (int i = 1; i < n; ++i) {
            int a, b, c; scanf("%d%d%d", &a, &b, &c);
            add_edge(a, b, c);
            add_edge(b, a, c);
        }
        vis[1] = 1;
        dfs(1, 0);
        printf("%d\n", ancnt);
        for (int i = 0; i < ancnt; ++i)
            printf("%d%c", ans[i], i == ancnt - 1 ? '\n' : ' ');
    }
    return 0;
}

複雜度分析

• 時間：O(N)，每條邊訪問一次。
• 空間：O(N)，鄰接表 + 遞歸棧 (深度 ≤ N，需注意棧溢位，可改迭代或增大棧)。

關鍵點總結

• 樹上貪心：從葉子向根決策，局部最優推導全局最優。
• 狀態傳遞：返回值表示「到父節點的邊是否已被覆蓋」。
• 去重邏輯：sum[u] ≥ 1 表示子樹已有人選中，避免重複選點。