题意简述
n个点的边带权树,给m条关键的链。把树上一条边的权值变为0,使得m条链的和中,最大值最小。 n,m<=1e5。
思路
二分最大值k。现在考虑如何检验一个k。
找到所有链和>k的链,设这里面最长的链长度为S,有C条这样的链。用树链剖分找到被所有C条链都覆盖的边。设边权为w,如果S−w<=k,又因为这条边被所有和>k的链都覆盖了,所以,将这条边边权设为0,就珂以把所有和>k的链修♂正回来。那就满足条件了,检验结果为true。
然后就这样二分即珂。
关于如何求被所有链都覆盖的边
如果您足够明智,跳过这个部分好了。
开一颗临时的树,所有边权为0,树链剖分维护:对于所有和>k的链(a,b),在链上的边权都+1。
然后只要找边权=C的边即珂。
但是树链剖分维护的是点权,怎么把边权转化成点权呢?只要把一条边的权值,记录在这条边的儿子上即珂。然后我们对于链(u,v)作加法操作的时候,记得把LCA(u,v)的操作给撤回掉(就是减掉),因为这个是多算的。
代码
1 |
|