由于咕掉的题解太多了，所以只能趁改完不动题的时间，来补补坑qwq，还是太弱了。
考试过程：
到新机房的第一次考试，貌似海星？
第一题一开始就觉得是个贪心，但以为所有小怪兽都要打完，所以想复杂了，但后来发现只要每个人都有怪兽打就吼了，然后显然二分答案，1h 打完。
T2没什么思路，想拆柿子，但没什么用，只qj了链的测试点，用来跑所有测试点竟然得了40pts。
T3一眼看错题，然后一眼wqs二分，然后调到考试结束也没调出样例。
题解：
T1 kill：
先把人和怪兽得坐标sort一下。
显然这n个人打怪兽的最长时间是单调的，然后直接二分答案即可，check时贪心的选择前面的怪兽。
T2 beauty：
类似于换根dp的思路，分别考虑子树内和子树外的点对产生的贡献，记$cnt[x]$ 为以$x$为根节点的子树内关键点的个数，那么对于，每个点，考虑所有的关键点在这一个点产生的贡献，子树内有$cnt[x]$个，那么子数外就有$2*k-cnt[x]$个，那么这些点配对的话，经过这一个点，即经过一个单位的距离，产生贡献就是$min(cnt[x],2*k-cnt[x])$，$dfs$一遍即可。
T3 wight：
考试时看错题，以为只要有一个最小生成树包含那条边即可，但实际上是要所有的最小生成树都要包含那条边。
我们可以先用kruscal 跑出一个最小生成树，那么他现在树边已经在最小生成树上了，所以我们对树边和非树边进行分类讨论。
对于非树边，因为只有树边才会被他替换下去，所以我们考虑树边对他的影响，考虑这条非树边两个端点的简单路径，加上这条非树边就会构成一个环，对于一个环，任意去掉一条边他还能够连接起n个点，所以这条非树边只要不是这个环上最大权值就可以，即MST上路径最大权值，树剖维护即可，然后把这条非树边本来的权值更新到线段树里边，后面树边情况要用到。
对于树边，我们考虑非树边对他的影响，同上，所有能够与他成环的非树边，只要有权值比他小的，就可以把它替换掉，所以每条树边的答案是所有与他成环的非树边的最小值减一，还是树剖维护。
注意：