[P4886]快递员

题目链接

题解

这个淀粉质点分治有点意思,与其他的点分治的题目不同的是,这题目并没有让你费劲心思怎么去用log的复杂度进行内层的统计,而是让你想到如何确定当前答案是否最优。
(下面不会讨论点分治的具体实现,此题不适合作为点分治入门题)

在此我们可以将情况分为两种:
1. 点对内

如图,我们的树长这样(假设边权全部为1),标红的是一对点对(6,7),当前的根为1
现在的问题是,当前求出来的答案 ans=4 是最优答案吗?
是!
显然如果如果往2或5走并不会影响答案,而往其他子树走,答案都要增加。
这时输出最优答案

(开始复读)

  1. 点对间
    图2
    如图,我们的树长这样(假设边权全部为1),标红的是一对点对(8,7),标绿的是另一对(6,4),当前的根为1
    现在的问题是,当前求出来的答案 ans=6 是最优答案吗?
    是!
    显然如果如果往绿点或5红点走并不会影响答案,而往其他子树走,答案都要增加。
    这时输出最优答案

(复读结束)

但是还没完,就刚刚两个点对的那幅图来说,我们显然不希望走没有点对经过的边,因此你可以看到 solve 函数中最后并没有对每个子树都递归。

代码

代码有点虚长,都是假的^_^

发表评论

电子邮件地址不会被公开。 必填项已用*标注