NOI2013 快餐店
图片炸了,难过。本地也没有存。
Sol.
一道很经典的基环树上dp题。调了一年。
首先,如果没有环的话,这就是一道简单的求树上重心的题目。众所周知,树的重心一定在直径的中点上。
但是现在在一个基环树上做,应该怎么求呢?我们先画一个图:
为了方便,我们先设边权全部为 \(1\)。
首先,我们可以想到断一条环上的边,然后求断边后的树的直径。
略证:考虑到直径一定不会经过一整个环,所以依次断边后求直径一定不会漏掉真正的直径。
这样的复杂度是 \(O(n^2)\) 的,我们考虑一下如何优化。
在刚刚的过程中,我们从环上的第一条边一直到最后一条边依次断开,而我们每次断开都要重新计算一次直径,这中间显然是有重合的部分的,于是我们可以考虑用类似于 dp 的东西优化。
考虑有两种情况:
- 直径没有经过环;
- 直径经过了环。
第一个情况很好搞,第二种情况略有麻烦,也是我们刚刚复杂度的瓶颈所在。
先上结论:
- 记 \(pre_i\) 表示 \(i\) 点之前某以环上节点为根节点的子树的直径加上该点距离环上 \(1\) 号点的距离的最大值;
- 记 \(suf_i\) 表示 \(i\) 点之后某以环上节点为根节点的子树的直径加上该点距离环上 \(m\) 号点的距离的最大值;
- 记 \(pres_i\) 表示 \(i\) 点之前环上某两节点的子树直径加上两点之间的距离的最大值;
- 记 \(sufs_i\) 表示 \(i\) 点之后环上某两节点的子树直径加上两点之间的距离的最大值;
- 记 \(w_{(i,j)}\) 表示 \(i,j\) 两点的距离。
那么第 \(i\) 号点的答案即为 \(\max\{pre_i, suf_{i+1}, pres_i+sufs_{i+1}+w_{(1,m)}\}\)。
最终答案即为 \(\min\limits_{i=1}^{m-1}\{\max\{pre_i, suf_{i+1}, pres_i+sufs_{i+1}+w_{(1,m)}\}\}\)
是不是到现在已经有些晕了?没关系,我们从图上举例说明一下。
例如,我们现在有一只删了一条环边 \((4,5)\) 的基环树。
我们仔细复盘一下刚刚的几句话。
先看 \(pre_i\) 和 \(suf_i\)。由于两个很像,所以重点解释 \(pre_i\)。
记 \(pre_i\) 表示 \(i\) 点之前 \(//\) 某以环上节点为根节点的子树的直径 \(//\) 加上该点距离环上 \(1\) 号点的距离 \(//\) 的最大值。
形式化的来说,我们要找的就是:
\(pre_i=\max\limits_{j=1}^{i}\{dep_j+w_{(1,j)}\}\)
来看张图。
可能有多种方案,图中仅展示一种。
图中绿色的部分即为 \(pre_4\),橙色的部分即为 \(suf_5\)。
可以看出来 \(pre_i\) 和 \(suf_i\) 其实就是一棵子树的直径 \(+\) 它前面(后面)的链的长度。
接下来再看看 \(pres_i\) 和 \(sufs_i\),同样重点解释 \(pres_i\)。
记 \(pres_i\) 表示 \(i\) 点之前 \(//\) 环上某两节点的子树直径 \(//\) 加上两点之间的距离的最大值。
形式化的来说,我们要找的就是:
\(pres_i=\max\limits_{j=1}^{i}\{dep_i+dep_j+w_{(i,j)}\}\)
再来看张图。
可能有多种方案,图中仅展示一种。
图中蓝色的部分即为 \(pres_4\),黄色的部分即为 \(sufs_5\)。
好,弄清楚这 \(4\) 个,我们来看看结果的式子:
那么第 \(i\) 号点的答案即为 \(\max\{pre_i, suf_{i+1}, pres_i+sufs_{i+1}+w_{(1,m)}\}\)。
我们考虑到删掉边 \((i,i+1)\) 的时候,直径有三种可能:
- 直径在 \([1,i]\) 之间;
- 直径在 \([i+1,m]\) 之间;
- 直径跨过了边 \((1,m)\)。
对于第一种情况,我们惊喜地发现,\(pres_i\) 即为我们所求。
对于第二种情况,我们再次惊喜地发现,\(sufs_{i+1}\) 即为我们所求。
对于第三种情况,我们发现,由于 \(pre_i\) 一直延伸到 \(i\),\(suf_{i+1}\) 一直延伸到 \(m\),所以我们再加上 \(w_{(1,m)}\) 即可,也就是 \(pre_i+suf_{i+1}+w_{(1,m)}\)。
最后我们遍历一遍,统计最小值即可。
Code
1 |
|
- 标题: NOI2013 快餐店
- 作者: 夏佑 | XiaU
- 创建于 : 2022-09-01 00:00:00
- 更新于 : 2023-09-15 09:13:54
- 链接: https://summace.cc/LGP1399/
- 版权声明: 本文章采用 CC BY-NC-SA 4.0 进行许可。