树上好题

/ll

P11627 [迷宫寻路 Round 3] 游戏 ​

给你一颗树，树上的边权是 $1,2,...n-1$ 的一个排列，你要选出一个点 $t$ 和边权，让 $\sum _{i=1}^{n}di{s}_{i,t}$ 最小.

其实出题人包装了一下这个题目.

首先显然换根，则你能知道所有边的贡献次数，贪心填边权即可，转移的时候发现改变的贡献是 $O(1)$ 个的.

比较想提的就是用权值线段树维护最后的答案.

权值线段树上，考虑左儿子和右儿子都处理出了答案，则把右儿子答案做一个偏移即可，偏移量就是 $cn{t}_{ls}\times su{m}_{rs}$，即 $an{s}_p=an{s}_{ls}+an{s}_{rs}+cn{t}_{ls}\times su{m}_{rs}$.

P6419 [COCI 2014/2015 #1] Kamp ​

给你一棵树，树上有 $k$ 个关键点，对于每个点 $i$ 求从这个点开始最少走多久能走完所有关键点.

容易发现，我们走出来的是一个所有关键点连通的边集，但是我们不用每个边都走两边走完，可以省出一个从根开始的最长链来.

而前者所有关键点连通的边集的长度和可以计算边的贡献得到，同前面那题转移的时候发现改变的贡献是 $O(1)$ 个的，后者是换根经典题.

【UER #12】电网检修 ​

给你一棵树，有两个人，她们距离不能超过 $k$，树上每个节点至少被她们其中一个到达过，求最小时间.

考虑无 $k$ 的限制，则不用每个边都走两边走完，可以省出一个直径的距离.现在加上 $k$ 的限制，注意到 $k\ge \mathrm{最}\mathrm{大}\mathrm{深}\mathrm{度}$ 的时候，可以构造省 $min(\mathrm{直}\mathrm{径},k)$，显然优了.

$k<\mathrm{最}\mathrm{大}\mathrm{深}\mathrm{度}$ 的时候考虑每一个 $\mathrm{子}\mathrm{树}\mathrm{深}\mathrm{度}=k$ 的节点，则构造大致是一个节点在里面走完，另一个在这个点等，最后就能让上面的人省 $\mathrm{最}\mathrm{大}\mathrm{深}\mathrm{度}-k$ 步，下面的人省 $\mathrm{最}\mathrm{大}\mathrm{深}\mathrm{度}$ 步.最优性证明参考官方题解.