CF 196 Div 2 D：樹形 DP 求可能藏書位置

題目大意

樹上 n 個節點，m 個已知受影響節點，傷害範圍 d。書可能在某節點，若該節點到所有受影響節點的距離均 ≤ d。求可能節點數。

解法：樹形 DP 維護最遠受影響距離

• dp[u][0/1]：以 u 為根的子樹內，距離 u 最遠和次遠的受影響節點距離。
• dir[u][0/1]：對應的子節點方向。
• 第一次 DFS 自底向上計算子樹內最遠距離。
• 第二次 DFS 自頂向下，利用父親信息更新 dp[u][*] 為全樹最遠距離。
• 最終統計 max(dp[u][0], dp[u][1]) ≤ d 的節點數。

代碼片段 (C++)

void dfs(int u, int pre) {
    if (vis[u]) dp[u][0] = dp[u][1] = 0;
    else dp[u][0] = dp[u][1] = -INF;
    for (int v : G[u]) if (v != pre) {
        dfs(v, u);
        // 更新 dp[u] 使用 dp[v]
    }
}
void dfss(int u, int pre) {
    // 利用父親信息更新子節點
}