This way 题意: 给你n个点,让你在其中选k个点作为特殊点,使得所有点到其中距离自己最近的特殊点的距离最大值最小,求这个值 题解: n只有60,那么翻译一下这个就是重复覆盖问题。 那么我们只需要二分一下答案,将所有小于等于mid的值加到舞蹈链中,再跑一下即可。 注意其中的优化: 由与deep就是当前使用的点数,那么当deep>k的时候return,注意不能直接做这个判断: if(
This way 题意: 给你一棵树,两种操作: 1.将x到y的路径上的所有点的权值+k 2.将x到y路径上的所有边的权值+k 所有操作结束后问你所有的点权和所有的边权 题解: 这道题用树链剖分估计会T,因为它是 n l o g 2 n nlog^2n nlog2n的。 由于每次加的一定是一条链或者两条链,那么我们只需要用前缀和的思想去做即可,也就是说加点权的时候在x的位置加上k,y的位置