Luogu4183 [USACO18JAN] Cow at Large P

发表于 分类于 ， ， 阅读次数：

题意：有一棵 个节点的树形迷宫，叶节点是出入口。

现在有一个人闯入了迷宫深处，他达到出口就可以逃离。

可以在出入口放置守卫，守卫的移动速度和闯入者相同，若闯入者和守卫相遇则被抓住。

守卫和闯入者在移动过程中均可以观察到对方的位置，而后决策。

对于闯入者可能的每个起点，问至少需要多少个守卫才能确保闯入者无法逃脱？

，时限 。

先来观察一下性质。为了方便，不妨将起点置为根。

  • 守卫的目标相当于封锁所有的叶节点，如果这一目的达到，接下来就是瓮中捉鳖。

  • 如果闯入者来到了某个没有守卫的子树，就可以一路向下到达叶节点。由于移动速度相同，守卫是追不上他的。

  • 对于某个点，若某个叶节点 到达该子树的距离，不超过根到该点的距离，则称为可以封锁。（在 放一个守卫，即可赶在逃脱者到来之前到达该点）

  • 若某个点可以封锁，则该点的子树也可以封锁。

设可以封锁的点集为 ，我们可以支付一个守卫封锁一个点，使得其子树失效。我们的目标是封锁整个 。我们又知道 是若干个子树的并集，故可以得到如下贪心：

在所有可封锁的点中，去掉有祖孙关系的点，留下尽量浅的点，它们（称为“表面点”）的个数即为答案。

若对每个起点做一次贪心，复杂度是 的，无法通过。

考虑使用点分树，每个点出发到达的联通块会被剖分成 个部分，每个部分有一个必经点。

对于点分树上的某个分治块，可以视为有根子问题，求出深度 。

某个从 而来的询问为：查询除去某棵子树的部分中,满足 的“表面点”个数。

“表面点”可以转化为：若父亲合法，则儿子不贡献。

由于若父亲能贡献，儿子必然贡献，我们可以在父亲处扣除儿子的贡献。

设 为 的儿子个数，则 的点权为 。不难发现，若选择一整个子树，贡献恰为 。

( 几乎总是等于度数，特别地，根的 应该恰好是度数，根贡献到自己只有叶节点，特判即可)

对前面的条件移项变为 ，这是个一维偏序，直接前缀和即可。

可以证明 的极差是 分治块大小 的，这样复杂度就是严格 。

对于某个子树不贡献的要求，可以容斥掉。

具体实现中，由于不需要在线回答，可以直接点分治。