CF161D Distance in Tree
DP狀態定義
根據子樹位置\(+\)路徑長度的統計設計狀態。
\(Dp_{u,j}\)表示在以 \(u\) 為根的子樹中，到 \(u\) 的距離恰好為 \(j\) 的節點個數。
初始化
\[dp_{u, 0}=1 \]
狀態轉移方程式
在合併子樹時來統計答案
\[ans = ans + \sum^k_{j=0}dp_{u,j} \times dp_{j,k-1-j} \]
處理完答案後再合併子樹：
\[dp_{u,j}=dp_{u,j}\sum^k_{j=1}dp_{v,j-1} \]
戳我看代碼
void dfs(int u, int fa) {
dp[u][0] = 1;
for (auto v : g[u]) {
if (fa == v) continue;
dfs(v, u);
rep(j, 0, k - 1) ans += dp[u][j] * dp[v][k - 1 - j];
rep(j, 1, k) dp[u][j] += dp[v][j - 1];
}
}
最重要的，樹上揹包！
例題：[CTSC1997] 選課
狀態定義
\(dp_{u,i,j}\)表示在 \(u\) 這裏，前 \(i\) 棵子樹，共計選擇 \(j\) 門課，共可以獲得的最大貢獻。
狀態轉移
自己先想想，很簡單，或者看代碼。
戳我看代碼
void dfs(int u){
for(auto v:graph[u]){
dfs(v); // 先遞歸求出子樹的答案
}
dp[u][0][1] = score[u];
for(int i=1;i<=graph[u].size();i++){
int v=graph[u][i-1];
int siz_v=graph[v].size(); // 標記1
for(int j=1;j<=m+1;j++){ // 至少選自己這門課，才可以考慮子樹
dp[u][i][j]=dp[u][i-1][j]; // 不選 v 子樹，直接繼承。
// 選 v 子樹，枚舉選多少
for(int k=0;k<=m+1;k++) if(j>k){//至少選自己這門課，才可以考慮子樹
dp[u][i][j]=max(dp[u][i][j],dp[u][i-1][j-k]+dp[v][siz_v][k])
}
}
}
}
