博客 / 列表

cqbzcdr - CF161D Distance in Tree + 樹上揹包

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 d

c++