树形 dp 做题笔记

在这个随笔中，会有笔者的一些做题笔记，包括但不限于树形 dp 的思想、解题技巧、代码实现等。

• CF1926G Vlad and Trouble at MIT \(\texttt{*1900}\)。

TAG: \(\texttt{树形 dp}\)

\(dp_{i,S,P}\) 为 \(i\) 的子树内是否存在 S 和 P 的状态。

转移方程为：

当 \(s_i\) 为 C 时

dp[x][0][0] += min({ dp[v][1][0] + 1, dp[v][0][1] + 1, dp[v][0][0] });
dp[x][1][0] += min({ dp[v][0][0], dp[v][1][0], dp[v][0][1] + 1 });
dp[x][0][1] += min({ dp[v][0][0], dp[v][1][0] + 1, dp[v][0][1] });

当 \(s_i\) 为 S 时

dp[x][1][0] += min({ dp[v][1][0], dp[v][0][1] + 1, dp[v][0][0] });

当 \(s_i\) 为 P 时

dp[x][0][1] += min({ dp[v][1][0] + 1, dp[v][0][1], dp[v][0][0] });

代码

• 1353F Decreasing Heights

TAG: \(\texttt{dp, 暴力}\)

枚举 \(a_{1, 1}\) 的值，然后算出 \((1, 1)\) 到 \((i, j)\) 的步数即 \(a_{i,j} = a_{1, 1} + i + j - 2\)，并暴力 \(dp\)。

代码