给定一个边带权的树和m次询问,每次询问给出点对(a,b),定义点对间的权值D(a,b){\rm dis}(a,x)+{\rm dis}(x,b),需要确定一个点x,使得最大的D(a,b)最小,求这个最小化的最大值。

n,m\leq 10^5,w_i\leq 10^3

Solution :

学习凯申的微操本领

随机选取一个点u,计算以u为根时的答案。对于每个询问点对(a,b),都被分成了(a,u),(u,b)两条链,对于端点a,b有两种情况:1. 在u的同一个子树内; 2. 在u的不同子树中。

假设当前取\max({\rm dis}(a,u)+{\rm dis}(u,b))对应的点对(x,y),设其值为D(x,y)

对于a,bu的同一个子树v中的情况,如果向其他子树任意子树v'中移动,当前最大值会变大,不利于答案;如果向子树v中移动,对于当前的最大值会减少2\times w_{(u,v)},对于其中一个端点在子树v中,另一个端点在其他任意子树v'中的点对,值不变,而对两个端点都不在v中的点对,则会增大2\times w_{(u,v)};那么考虑向v中移动什么时候会更优,显然是两端点都不在v中的最大值D(x',y')与当前最大值D(x,y)差值大于2\times w_{(u,v)},如果差值等于2\times w_{(u,v)},则移动后最大值不变,答案就是当前最大值。

而对于a,bu的不同子树v_1,v_2中时,向v_1,v_2两个子树中移动D(x,y)不会发生变化,但是其余值可能会增大或者减小,不可能让答案更优;如果向其他子树v'中移动,当前最大值一定会变得更大,答案更劣。

综上,如果有更优的情况,那么应该存在于对应的子树v中。但是如果每次只移动一条边,最差在一条链上要移动O(n)次,复杂度O(n^2),跟枚举每个点的暴力没任何区别;但是如果用点分治,每次可以把答案所在的范围缩小一半,至多需要迭代O(\log n)次就可以找到答案,所以点分之后\rm dfs一遍子树按照上述情况分类讨论即可,对于一个点的处理是O(n)的。总复杂度O(n\log n)

跟题无关的结论: 一个度数序列可以构成无向图,当且仅当: \forall k \in [1,n]\sum_{i=1}^k{d_i\leq k(k-1)}+\sum_{i=k+1}^n{min(d_i,k)}

树上问题 分治

2022.9.24
上一篇 «
2022.9.19补
» 下一篇
© 2017 - 2024 云雀.
...... visits · ...... visitors