树形DP($O(n)$)
给定一棵有N个节点的树(通常是无根树,也就是有N-1条无向边),我们可以任选一个节点为根节点,从而定义出每个节点的深度和每棵子树的根。在树上设计动态规划算法时,一般就以节点从深到浅(子树从小到大)的顺序作为DP的“阶段”。DP的状态表示中,第一维通常是节点编号(代表以该节点为根的子树)。大多数时候,我们采用递归的方式实现树形动态规划。对于每个节点x,先递归在它的每个子节点上进行DP,在回溯时,从子节点向节点x进行状态转移。
没有上司的舞会
$f[u][c]$
$第一维:节点编号$
$第二维:状态(选u或不选u)$
$含义:以u为根的子树的最大快乐指数$
$从根节点开始递归:f[u][1]=h[u]+sum(f[j][0]),f[u][0]=sum(max(f[j][0],f[j][1]))$
Solution
树的遍历:树的重心
找树的直径:
1.任取一个点作为起点,找到距离该点最远的一个点u(u必为直径上的一个端点)。(DFS/BFS)
2.再找到距离u最远的一个点v(u-v是一条直径)。(DFS/BFS)
树的最长路径
$随便选一个点作为整棵树的根节点$
$状态表示:以u为根节点的子树的最大深度$
$状态计算:以u的子节点为根节点的子树的最大深度+u与子节点的边的权值$
$从根节点开始遍历每棵子树,求得每棵子树的最大深度和次大深度,计算每棵子树的最大直径(最大深度+次大深度),取max$
Solution
树的中心
$最远距离分为向上最远距离和向下最远距离$
$向下最远距离可以从根节点开始向下遍历,树形DP(d1[u]=max(d1[j])+w[i])$
$向上最远距离也可以从根节点开始遍历,树形DP$
$如果j是d1[u]上的点,则up[j]=max(d2[u]+w[i])$
$否则up[j]=max(d1[u])+w[i]$
Solution
数字转换
$求约数之和:枚举每个数x的其倍数y加上x$
$以约数之和为父节点,该数为子节点建树$
$求树最长直径$