1. 小G有一个大树（求树的重心）
删除该点后最大连通块的节点数最小
设f[x]表示以x为根的子树大小，那么删除x之后的各子树大小为f[to]和n-f[x]
求max(max(f[to]),n-f[x])的最小值以及最小值所对的x
2.没有上司的舞会
儿子和父亲不能同时选择
设dp[x][0/1]表示x节点不选/选，他的子树快乐最大值是多少
dp[x][0] += max(dp[x][0],dp[x][1]);
dp[x][1] += dp[x][0];
最后答案为max(dp[x][0],dp[x][1]);
3.Cell Phone Network
一个点可以关联它与它相邻的点
设dp[x][0/1/2]表示被他的儿子/父亲/自己关联
dp[x][0] += min(dp[to][0],dp[to][2]) 特殊情况是儿子都是被儿子的儿子关联，没有儿子能关联他，这时要加上min(dp[to][2]-dp[to][0]) > 0
dp[x][1] += min(dp[to][0],min(dp[to][1],dp[to][2]))
dp[x][2] += min(do[to][0],dp[to][2]);
最后答案为min(dp[to][0],dp[to][2]);
4.二叉苹果树
选儿子必须选父亲->看成树上依赖背包
dp[x][j]表示i为根的子树内连续选j条边的最大苹果树
dp[x][j] = max(dp[x][j],dp[x][j-k-1]+dp[to][k]+w) 注意j要倒序处理，防止重复选择一颗子树
答案为dp[1][m]
5.树上子链
带权树上直径
经过x的最长链为最长链+次长链
6.Rinne Loves Edges
弱化版的吉吉国王
7.吉吉国王
最长长度最小（二分）
dp[x]表示把x子树内的叶子切断的最小代价
当w>规划的最长长度 dp[x] += dp[to];
当w<规划的最长长度 dp[x] += min(dp[to],w);