算法提高课：1.7 树形DP
考虑到链一定是连续的,且在树上有两种情况:
蓝色表示,链上深度最浅的点是链的一端的情况.
而红色表示,链的两端都不是链上最浅的点.
而显然,对于蓝色的链,其最浅的点仍然可以向上拓展,而红色不行.
那么,问题就可以用树形dp解决了.
设f[u]表示以u为链的一端,且u为链上最浅的点的最长链的长度
这样我们就可以得到最长的蓝色链,转移方程也不难得出:
那么红色的呢?考虑到每一条红色链都能被它的最浅的点分成两条蓝色链,那么在决策点u时顺便更新答案即可