树形dp

• 树的遍历，用DFS从根节点开始进行记忆化搜索
• 从树最深处开始往回进行DP，用子节点dp值来更新父节点dp值

板子

void dfs(int u)
{
	dp[u][...] = ...; 			//初始化
	for(int i=0; i < edge[u].size(); i++)	//遍历处理u的子节点v
	{
		int v = edge[u][i];
        	dfs(v);				//深搜子结点
        	dp[u][...] = ...;		//状态转移方程
   	}
}