Tree DP

Problem:给定一颗树,给每个节点都染上颜色使没有两个相邻的节点都染上颜色。

Solve:每个节点记录两个最大值，1.这个节点染色的最大值B[u]  2.这个节点不然色的最大值W[u] 

初始叶子有B[v]=1,W[v]=0,dfs一遍对root取max(B[root],W[root])。

 

Balancing Act

dfs一遍标记以每个节点为根的子树总的节点数，tree dp 一遍得出删除每个节点的blance，O(N)扫一遍取最小。