RainAir
My OI Blog
RainAir
「CF835F」Roads in the Kingdom

题目大意

有一棵基环树,现在你需要从基环树上选择一条边被删除,满足:
1. 删除后形成的是一棵树(不是森林)
2. 删除后的直径尽量小

并且求出最小可能的直径

题解

首先基环树求直径大家都会。。。Island 岛屿(虽然由于我太菜至今还没卡常成功)
然后这个题我们考虑如何删除一条边之后快速算出直径。
我们只考虑最长路径跨过环的情况(不跨过环的可以轻松处理)
对于每个子树做直径 dp 是必须的,然后我们考虑如何快速换边。。
首先我们考虑我们暴力如果枚举每一对有序对 $(x,y)$ 并且默认删除了 x 逆时针方向的第一条边的话,这种暴力能遍取每一种可能的情况的。
那我们就考虑现在做到了点 $x$ (也就是删除了它逆时针方向的第一条边),令 $dis_v$ 表示 $v$ 到 $x$ 的距离,$val_v$ 表示 $v$ 的子树的最长且一端在该点上的链。那么我们分别用 $set$ 维护处 $val_v+dep_v$ 和 $val_v-dep_v$ 就可以了。
现在考虑如果 $x$ 变换为顺时针方向上的第一个点 $y$ ,会造成什么影响。
我们设环长为 $sm$,那么显然每次操作只会影响到 $dis$,我们设边 $(x,y)$ 的权值为 $w$,发现 $dis_x = dis_x + sm – w, dis_y = dis_y – w(\forall y \neq x)$(即使是赋值操作也写成加法统一比较好)
相当于单点加和全体减了,由于查询的时候是对 $dis$ 做差,所以我们可以无视第二个操作。
然后就码码码就行了。
这个题貌似和 BZOJ3242 撞了,双倍经验。。。

赞赏
知识共享许可协议
本文链接: https://blog.aor.sd.cn/archives/822
如文中无特殊声明,本文采用 CC BY-NC-SA 4.0 进行许可,转载请说明出处!
希望 CSP 不要翻车,希望省选不要翻车
https://secure.gravatar.com/avatar/97c17c68a1e55e11bb5558bc0f10cc0d?s=256&d=mm&r=g

RainAir

文章作者

一个OIer。

发表评论

textsms
account_circle
email

RainAir

「CF835F」Roads in the Kingdom
题目大意 有一棵基环树,现在你需要从基环树上选择一条边被删除,满足: 1. 删除后形成的是一棵树(不是森林) 2. 删除后的直径尽量小 并且求出最小可能的直径 题解 首先基环树求直径…
扫描二维码继续阅读
2019-08-30
标签
近期评论