url: https://www.luogu.com.cn/problem/P1453tag:动态规划，图论，基环树，树形DP思路：基环树是一种特殊的图结构，可以看作是在一棵树的基础上加入一条额外的边，从而使图中恰好出现一个环，也称作单环图或唯一环图（unicyclic graph）。其主要特点包括：连通性：基环树是连通图，任意两个顶点之间都有路径…

url: https://www.luogu.com.cn/problem/P1272tag:动态规划，树形DP思路：简单的树形DP和背包结合。令 f[u][j] 表示以u节点为根的子树在需要取出j个节点时最少需要断的边。最后在输出答案的时候在所有节点中选择一个答案最小的，注意选择其他节点为根节点时需要断去父节点和其之间的一条边。最后输出答案即可。…

url: https://www.luogu.com.cn/problem/P3177tag:动态规划，树形DP思路：用 f[u][j] 表示以u为根节点的子树中，恰好有j个黑点时的收益。之后就是和分组背包类似的思路，对于每一个相连的节点，由当那个节点取k个黑点时更新过来，在不同的k值之间取一个最大值。使用 (k * (m - k) + (s[v]…

url: https://www.luogu.com.cn/problem/P3621tag:动态规划，树形DP思路：用 tr[u][0/1] 来存二叉树。做两次dfs第一次求出最大的深度和最小的深度，如果相差大于1直接输出-1。第二次dfs从下到上递归，设计返回值为0/1/2分别表示都是浅层，都是深层和混合。当左边为浅层，右边为深层或者左边为混合…

url: https://www.luogu.com.cn/problem/P1273tag:动态规划，树形DP，背包DP思路：用 f[u][j] 表示第u个节点选择j个用户时的盈利数。使用分组背包的思想。状态转移方程为 f[u][k] = max(f[u][k], f[u][k - l] + f[j][l] - w[i]) 其中w表示如果将节点j…

url: https://www.luogu.com.cn/problem/P2986tag:动态规划，树形DP，USACO，2010思路：可以参考 洛谷P3478 POI 2008 STA-Station 都是要求出当某一个节点为根时其他点到这个根的距离，我们可以用一次dfs来求出以任意选的一个节点作为根节点时的答案，比如选择节点1为根节点。然后…

url: https://www.luogu.com.cn/problem/P2014tag:动态规划，树形DP，CTSC/CTS，1997思路：和背包比较像，但是有一点区别的是对如果某个节点要选，也需要将其选不同数量节点的情况，分别更新，也就是说不知道每个点的“体积”是多少。因为要选一门课需要将其有依赖的课也选。所以需要从小更新到大。如果将0也算…

url: https://www.luogu.com.cn/problem/P4084tag: 动态规划，树形DP，USACO，2017思路：用树形DP来解决。定义数组 f[i][k] 表示以i为根节点且i涂的颜色为k时的方案数。然后根据k的不同分别更新即可。最后答案输出以1为根节点时3个颜色方案数之和（以其他节点为根节点也可以）。代码：#incl…

url: https://www.luogu.com.cn/problem/P2015tag：树形DP，动态规划思路：用数组f[u, j] 表示以u为根节点使用不超过 j 条边时最大的苹果数量。和背包问题有点不同的是，对于每一个点来说，假如需要用到某一个子节点来更新，则需要与之想连，所以其实是需要预备那个子节点所连的所有边 + 1的边来更新。所以状…

url: https://www.luogu.com.cn/problem/P3047tag:树形DP, USACO, 2012思路：用f[u,m] 表示以u为根节点，向下走出不超过m步时的权值，d[u, m] 表示以u为根节点，向上或向下走不超过m步时的权值。利用两次dfs分别求出f和d，最后输出每个节点作为根节点时的权值和即可。代码：#incl…