FZU 2169 Shadow：樹形 DP 計算叛軍總數（鄰接表存圖）

題目大意

N (≤ 100000) 個城市形成樹（N-1 條邊），城市 1 為王都。K 個城市有軍隊（不含王都），每城市有叛軍數 A_i。軍隊沿最短路（樹上唯一路徑）向王都進軍，消滅沿途城市叛軍。求總共消滅叛軍數。注意：多支軍隊經過同一城市，叛軍只被消滅一次。

樹形 DP 思路

以王都 1 為根 DFS。定義：

• hasArmy[u]：子樹 u 內是否有軍隊（含 u 自身）。
• dp[u]：子樹 u 內需消滅的叛軍總數（去重）。

遞歸：

dfs(u):
    dp[u] = A[u]
    hasArmy[u] = (u 在軍隊列表中)
    for v in children(u):
        dfs(v)
        if hasArmy[v]:
            hasArmy[u] = true
            dp[u] += dp[v]

最終答案 dp[1]。因為只有通往有軍隊葉子的路徑上的城市才會被經過，叛軍只算一次。

完整 C 代碼

#include 
#include 

typedef struct Node { int id; struct Node* next; } *LIST, NODE;
LIST adj[200005];
int dp[200005], hasArmy[200005], val[200005], vis[200005];

void dfs(int u) {
    vis[u] = 1;
    dp[u] = val[u];
    for (LIST p = adj[u]->next; p; p = p->next) {
        int v = p->id;
        if (vis[v]) continue;
        dfs(v);
        if (hasArmy[v]) {
            hasArmy[u] = 1;
            dp[u] += dp[v];
        }
    }
}

int main() {
    int n, k;
    while (scanf("%d%d", &n, &k) == 2) {
        for (int i = 1; i <= n; i++) {
            hasArmy[i] = vis[i] = 0;
            adj[i] = (LIST)malloc(sizeof(NODE));
            adj[i]->next = NULL;
        }
        for (int i = 1; i <= n; i++) scanf("%d", &val[i]);
        for (int i = 0; i < k; i++) {
            int x; scanf("%d", &x);
            hasArmy[x] = 1;
        }
        for (int i = 1; i < n; i++) {
            int u, v; scanf("%d%d", &u, &v);
            LIST p = (LIST)malloc(sizeof(NODE));
            p->id = v; p->next = adj[u]->next; adj[u]->next = p;
            p = (LIST)malloc(sizeof(NODE));
            p->id = u; p->next = adj[v]->next; adj[v]->next = p;
        }
        dfs(1);
        printf("%d\n", dp[1]);
        // 釋放內存略
    }
    return 0;
}

關鍵點總結

1. 樹上唯一路徑性質：軍隊到根的路徑即為其祖先鏈。
2. DP 合併：子樹有軍隊則父節點必經過，叛軍累加；無軍隊子樹完全忽略。
3. 鄰接表存圖，遞歸 DFS，N=1e5 需避免棧溢出（可改迭代或增棧）。
4. 多測試案例需完整清空數組與釋放內存。