iceylemon 的程式小空間
  • iceylemon 的程式小空間
  • 小知識
    • 施工中的筆記
      • Tree
        • 重心剖分
    • Dynamic Programming
      • DP Time
        • 暖身題單
        • LIS と LCS
        • 二維 DP
        • 背包 DP
        • 區間DP
        • 環狀DP
        • 狀壓DP
        • 樹DP
        • 數位DP
      • DP OPT Time
        • 前綴和優化
        • 矩陣快速冪優化
        • 資料結構優化
        • SOS 優化
        • 單調隊列優化
        • 斜率優化 (Convex Hull Trick)
        • 四邊形優化
        • Aliens 優化
        • Slope Trick
  • 隨筆
    • 題解
      • CF 1557D
Powered by GitBook
On this page
  • 介紹
  • 例題

Was this helpful?

  1. 小知識
  2. Dynamic Programming
  3. DP Time

樹DP

施工中

Previous狀壓DPNext數位DP

Last updated 3 years ago

Was this helpful?

介紹

這是一個恐怖的章節，因為我不會樹 DP 樹 DP 比背包還要博大精深，他自己一個 DP 就延伸出很多分支了 但也因為這樣，他非常重要，可以說是 DP 的非常大個章節

主要有以下分支：

  1. 普通DP

  2. 樹上背包

  3. 換根DP

  4. 基環樹(只有一個環的樹)

  5. 其他毒瘤(虛樹、長鍊剖分)

例題

換根DP
TOI 2020 pB
TOI 2020 pB 推廣題
洛谷樹DP