考虑到链一定是连续的,且在树上有两种情况:
蓝色表示,链上深度最浅的点是链的一端的情况. 而红色表示,链的两端都不是链上最浅的点. 而显然,对于蓝色的链,其最浅的点仍然可以向上拓展,而红色不行. 那么,问题就可以用树形dp解决了.
设f[u]表示以u为链的一端,且u为链上最浅的点的最长链的长度 这样我们就可以得到最长的蓝色链,转移方程也不难得出:
那么红色的呢?考虑到每一条红色链都能被它的最浅的点分成两条蓝色链,那么在决策点u时顺便更新答案即可
1072. 树的最长路径
1073. 树的中心
1075. 数字转换
1074. 二叉苹果树
323. 战略游戏
1077. 皇宫看守
