一、學習目標

• 掌握 樹上 DP 的三個典型套路：
  • 子樹 DP（自底向上）：狀態只看子樹（如最大匹配、子樹和）。
  • 換根 DP（rerooting）：先求某根的答案，再把根「沿邊轉移」到所有點。
  • 多狀態 DP：每個節點有多個「角色」（取／不取、覆蓋／未覆蓋）。
• 正確處理 轉移方向、重複計數避免、邊界初始化。
• 能把口訣化為模板：
  • 子樹 DP 常見：dp[u] = merge( dp[v] for v in children )。
  • 換根 DP：ans[v] = ans[u] + (n - 2 * size[v])（最經典的距離和換根式）。
  • 多狀態：對每個子節點先計「不選 vs 選」的貢獻，再挑最優組合。

二、觀念說明（程式觀念）

• 子樹 DP：先 DFS 到葉子，再回溯合併子結果。合併時，常見做法是先把「所有子樹的基準值」相加，再嘗試「在某個子上採取特殊動作」帶來的增益，從而取最大。
• 換根 DP（rerooting）：兩次 DFS。
  • dfs1(u,p): 算 subSize[u]、以及以某根（通常是 1）時 u 的基礎量（如到根的距離和）。
  • dfs2(u,p): 把根從 u 換到 v 時，推導 ans[v] 的關係（最常見的距離和公式如上）。
• 多狀態 DP：如 House Robber III / Binary Tree Cameras。狀態之間的「互斥」要清晰，轉移時注意只用已計好的子狀態。

三、CSES實戰演練

題目1:Tree Matching

原題:
https://cses.fi/problemset/task/1130

題意:
給一棵 n 點無根樹，選一些邊，使得任兩條選中的邊不共享端點（匹配）。求可選邊數最大值。

解題思路:

• 子樹 DP，兩態：
  • dp[u][0]：在 u 的子樹內最佳匹配數，且 u 沒有 跟子節點匹配。
  • dp[u][1]：在 u 的子樹內最佳匹配數，且 u 有 跟某個子節點匹配（恰配一條）。
• 轉移：
  • 先算 base = Σ max(dp[v][0], dp[v][1])（所有子樹各自最優，u 不強迫匹配）。
  • 若要讓 u 跟某個 v 匹配，則對該 v，子樹貢獻要改成 dp[v][0] + 1（因為 v 不能再與其子匹配了且新增邊 u-v），其餘子仍取 max(dp[v][0], dp[v][1])。
  • dp[u][1] = base + max_over_v( dp[v][0] + 1 - max(dp[v][0], dp[v][1]) )，若沒有子可配則維持 -inf/不取。
  • dp[u][0] = base。

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

const int INF_NEG = -1e9;
int n;
vector<vector<int>> g;
vector<array<int,2>> dp; // dp[u][0/1]

void dfs(int u, int p){
    int base = 0;
    for(int v: g[u]) if(v!=p){
        dfs(v, u);
        base += max(dp[v][0], dp[v][1]);
    }
    dp[u][0] = base;

    int bestGain = INF_NEG;
    for(int v: g[u]) if(v!=p){
        int gain = dp[v][0] + 1 - max(dp[v][0], dp[v][1]);
        bestGain = max(bestGain, gain);
    }
    dp[u][1] = (bestGain==INF_NEG ? INF_NEG : base + bestGain);
}

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n;
    g.assign(n+1, {});
    for(int i=0;i<n-1;i++){
        int a,b; cin>>a>>b;
        g[a].push_back(b); g[b].push_back(a);
    }
    dp.assign(n+1, {0, INF_NEG});
    dfs(1, 0);
    cout << max(dp[1][0], dp[1][1]) << "\n";
    return 0;
}

題目2:Tree Distances II

原題:
https://cses.fi/problemset/task/1133

題意:
給一棵 n 點樹，對每個節點 u，輸出 sum_{v} dist(u, v)。

解題思路（換根 DP）

• 第一次 DFS：以 1 為根，算
  • sz[u]：u 子樹大小；
  • dp1：ans[1] = Σ dist(1, v)，可在一次 DFS 中累積（把每條邊走一次即統計深度和）。
• 第二次 DFS（reroot）：從 u 推到相鄰 v 時，距離和會
  • ans[v] = ans[u] + (n - 2*sz[v])（把根從 u 換到 v：v 子樹裡的點距離 -1，其餘 +1）。

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

int n;
vector<vector<int>> g;
vector<long long> ans;
vector<int> sz;

void dfs1(int u, int p, int depth, long long &sumDepth){
    sz[u] = 1;
    sumDepth += depth;
    for(int v: g[u]) if(v!=p){
        dfs1(v, u, depth+1, sumDepth);
        sz[u] += sz[v];
    }
}

void dfs2(int u, int p){
    for(int v: g[u]) if(v!=p){
        // reroot: move root from u to v
        ans[v] = ans[u] + (long long)n - 2LL*sz[v];
        dfs2(v, u);
    }
}

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    cin>>n;
    g.assign(n+1, {});
    for(int i=0;i<n-1;i++){
        int a,b; cin>>a>>b;
        g[a].push_back(b); g[b].push_back(a);
    }
    ans.assign(n+1, 0);
    sz.assign(n+1, 0);
    long long sumDepth = 0;
    dfs1(1, 0, 0, sumDepth);
    ans[1] = sumDepth;
    dfs2(1, 0);
    for(int i=1;i<=n;i++){
        cout << ans[i] << (i==n?'\n':' ');
    }
    return 0;
}

四、Leetcode實戰演練

題目1:House Robber III

原題:
https://leetcode.com/problems/house-robber-iii/description/

題意:
二元樹，每個節點有金額。不能同時搶相鄰節點（父子不能同取）。求最大總額。

解題思路

• 兩態 DP：f(u,0)=u 不取時的最大值；f(u,1)=u 取時的最大值。
• 轉移：
  • f(u,1) = val[u] + Σ f(child,0)（取了 u，子都不能取）
  • f(u,0) = Σ max(f(child,0), f(child,1))（不取 u，子隨意取最佳）

/**
 * Definition for a binary tree node.
 * struct TreeNode { int val; TreeNode *left; TreeNode *right;
 *   TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *   TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *   TreeNode(int x, TreeNode *l, TreeNode *r) : val(x), left(l), right(r) {}
 * };
 */
class Solution {
    pair<int,int> dfs(TreeNode* u){
        if(!u) return {0,0}; // {notTake, take}
        auto L = dfs(u->left);
        auto R = dfs(u->right);
        int take = u->val + L.first + R.first;
        int notTake = max(L.first, L.second) + max(R.first, R.second);
        return {notTake, take};
    }
public:
    int rob(TreeNode* root) {
        auto [a,b] = dfs(root);
        return max(a,b);
    }
};

題目2:Binary Tree Maximum Path Sum

原題:
https://leetcode.com/problems/binary-tree-maximum-path-sum/

題意:
二元樹中任意兩節點之間的路徑和最大值（路徑必須連續向下或經過某節點轉彎；可為單點）。

解題思路:

• 遞迴函式回傳「從當前節點出發，向下延伸 的最大貢獻值」（負值視為 0 不延伸）。
• 同時在每個節點更新全域 ans = max(ans, leftGain + rightGain + val[u])。
• 回傳給父節點的值是 val[u] + max(leftGain, rightGain)。

class Solution {
    int best = INT_MIN;
    int gain(TreeNode* u){
        if(!u) return 0;
        int L = max(0, gain(u->left));
        int R = max(0, gain(u->right));
        best = max(best, u->val + L + R);            // 經過 u 作為峰頂
        return u->val + max(L, R);                   // 向上一條鏈
    }
public:
    int maxPathSum(TreeNode* root) {
        gain(root);
        return best;
    }
};