树形dp

树上做dp非常常见，因为树本身有子结构性质（树和子树）
一般解题思路：先把树转化为有根树（如果不连通的树，就加一个虚拟根，它连接所有孤立的树），然后在做dfs，递归到叶子节点，再一层层返回信息，就在这一步做dfs

P2015 二叉苹果树

定义状态 \(dp[u][j]\) 表示以节点u为根的子树上留j条边时

换根dp

写的比较好的博客

P3478 STA-Station

板子题，比较适合练手

二叉树做法

考虑左右节点的边的总数是一定的，所以我们枚举一个子树的边就可以了

void dfs(int u){
	for(int i=0;i<=num;i++){//num代表子树内边的数量
		dp[u][i]=max(dp[u][i],dp[lson][i],dp[rson][num-i]);
	}
}

多叉树做法

我们挨个子节点枚举，然后再枚举当前子节点v选的边数，剩下的就是1~v-1 的子节点保留的分叉数

void dfs(int u){
	for(auto v:b[u]){//v是u的子节点
		for(int i=num;i>=1;i--){//枚举要割几条边
			for(int j=0;j<=i;j++){
				dp[u][j]=max(dp[u][j],dp[u][i-j-1]+dp[v][j]+w[u]);//i-j-1因为连向v也算一条边
                //实际上是dp[u][v][j]=max(dp[u][v][j],dp[u][v-1][i-j-1]+dp[v][j]+w[u]压掉v一维所以枚举i时要倒叙枚举
			}
		}
	}
}

P1352 没有上司的舞会

典题，不多赘述

P2014 选课

树上背包板子题，我们设 \(dp[u][t]\) 在u子树内选t个点所得到的最大值
所以我们的我们的针对一个子树内进行操作，枚举所有的子节点，再枚举要在这个子树內选取的点的个数 \(t\)，再枚举一个在这个子节点的子树內枚举的点的个数 \(j\)

然后最后答案统计就是 \(dp[u][t]=dp[v][j]+dp[u][t-j]\)

一本通题解

T5：

神奇的一种转化，经典思路

考虑一条边对答案贡献了多少次

把用一条边把树分成两个部分，因为其是树边，所以一部分必然是一个端点的子树，另一部分是除去这个子树外的其余所有树，因为其说是至少一个端点是叶子节点，所以我们只要一部分一个叶子节点和另一部分的任意一个点组合即可

只需要统计一下该子树内的叶子节点和节点个数，然后另一部分的用总的减去该子树內的容斥即可

T6：

一个人走的情况就是求一下s能到达的最长距离，两个人的情况就是求一下树上最长链

额额额，手模出来的，再加上一些感性理解

树上最长链，可以求一下由这个点出发能到达这个子树的最远距离，然后最长链自然是用这个距离再加上另一条和这条路径不重复的最长路径，也就是在我们树形dp转移时统计一下最长和次长的距离即可（注意不可交，就是用其子节点转移即可）

注意，s能到的最长路径不能直接用你求树上最长链的答案，因为它是子树內的最长路径

T7：

巧妙地推式子题，考虑首先设我们以 \(i\) 为根时，包含 \(i\) 所构成的连通块并且满足有特殊值的方案数，这个是不好做的

考虑容斥，我们设 \(f[i]\) 为包含 \(i\) 所构成的连通块的总方案数，\(g[i]\) 为包含 \(i\) 所构成的连通块中不包含特殊值的方案数，最终答案即为 \(ans[i]=f[i]-g[i]\)

然后怎么求 \(f[i],g[i]\) ？

对于 \(f[i]=\prod_{j\in son[i]} (f[i]+1)\) 为什么呢，对于每一个子树都有 \(f[j]\) 种选的方案，还有一种不选 \(j\) 的方案

对于 \(g[i]\) 若其不为特殊点，则转移方式和 \(f[i]\) 一样，否则 $g[i]=0 $

然后注意因为是取完模之后，所以在求 \(ans[i]\) 的时候别忘了先加一个模数再取模