前言
依旧学到哪写到哪，依旧草履虫都能学会，依旧简单语言，依旧被 Xylophone 压力。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
正文
WHAT IS...
树形 DP，即在树上进行的 DP．由于树固有的递归性质，树形 DP 一般都是递归进行的． ——OI Wiki[1]
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
实现
问，为什么这么早就上例题？
答，不上例题没办法讲。
B2171 结点子树大小 / 依旧没有 ACGO 版本，哎呦我这不 ACGO 叔叔吗。
题目大意
给定一棵 nnn 个节点的树，其中根结点编号为 111。
然后，给定 n−1n-1n−1 条边（保证构成树），输入格式 uuu vvv，表示一条 uuu 到 vvv 的边。
求出每一节点的子树大小（包含当前节点）。
思路
注意到每个节点的子树大小都包含了自己+所有子树的大小，而叶子节点没有子树，所以子树大小只包含自身，即 111。
那么可以对于每一个非叶节点先处理子节点的子树大小，然后在自己的子树大小加上这个子节点的子树大小。
因为树的递归性质，我们可以递归处理子树。同时，还要多一个父节点参数来防止走回去。
对于根节点，我们在递归时给他来一个假爹 000 ，这样就能给根节点传 父节点 参数了。
> 那么递归的结束条件呢？很简单，当递归到叶子节点时，由于没有子节点，递归不会继续，变相实现了递归结束条件。
代码（参考注释食用）
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
例题，例题和例题，当然还有例题
P1352 没有上司的舞会 / A41048.【树形动态规划】没有上司的舞会
先处理子节点的最大值，再处理当前节点。
考虑给dp数组多开一个维度，dp[i][0]表示 iii 不参加的最大值，dp[i][1]表示 iii 参加的最大值。
转移方程（v代表子节点）：
* 当 iii 参加时，其直接下属不能参加，所以只能加上不参加的结果dp[v][0];
* 当 iii 不参加时，其直接下属可以选择参加或不参加，所以在两种结果取最大值：max(dp[v][0],dp[v][1])。
遍历v求解即可，注意要找根。
> 不加注释是因为带注释版本一个刷新被洛谷吃了。
----例题持续更新中，有意见请提出----
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
1. https://oi-wiki.org/dp/tree/ ↩︎
