树形dp,即在树上进行dp。
需要对树这一数据结构有清晰的了解。其中重点在于树的遍历、子树相关问题。
难点常常在于状态方程的书写。
例题
题意
树上每个结点有权值,要求在树上选一些点,满足有父子关系的结点只能出现一个,问选出的最大的权值和。
思路
用 \(dp[i][0/1]\) 表示 第 \(i\) 号结点选或者不选,令 \(x \in son[i]\) ,方程为
\(dp[i][0] += max(dp[x][0],dp[x][1])\) ,
\(dp[i][1] += dp[x][0]\)
标签:结点,树上,入门,树形,例题,dp From: https://www.cnblogs.com/re0acm/p/16607044.html