NOIP2024集训Day27 DP常见模型4 - 树形
E. [COCI2014-2015#1] Kamp
首先只考虑一个点，发现如果回到原来位置是比较好搞的，就每次走完子树的里面要的就上来，如果子树里面没有要走的就不走。
（大概是 \(f_x = \sum f_y + 2\cdot e_x\)，因为要走过去走回来，注意 \(y\) 要保证子树里面有人）
至于多个点换根 DP 即可。
然后考虑不走回来，那你少了的长度就是从最后一个人走回自己的距离。
那贪心的选离你最远的，思考一下发现是可以的因为可以最晚走到的条件是子树内除了自己没有人，安排一下子树的遍历顺序即可。
那这个对于每个点求距离它最远的人其实不难，就分成子树内和子树外，子树内好统计，子树外就维护子树内次小（不能跟最小在同一个儿子里面），然后要么从上面的 up 下来，要么在你这里开始往下（因为不能自己上自己下所以要维护次小）
标签：子树,Day27,树形,NOIP2024,集训,DP From： https://www.cnblogs.com/Leirt/p/18410480