【树】【容斥】【分治】tree

· · 个人记录

只要有信念，就一定能成功！ jaisuf8f7g9s9s8f9*

题意

给定一棵树，对树上每个点 u 定义集合 S_u=\{v\mid u\text{ 和 }v\text{ 的树上距离不超过 }d_u\}。

对于一个点集，如果其 S_u 的交非空，那么它是合法的，且贡献为点集大小的二次幂。

求所有合法集合选取方案的权值和。

分析

看上去很不可做，我们可以尝试寻找一种可能的思路，尽管它一开始可能是错误的，也可能为我们提供些许性质，指出通向正解的道路。

一种想法是枚举每个点被覆盖的次数，然后取三次幂（也就是可能形成的子集贡献和）加起来，然而这显然是错误的，因为每一种合法的情况都会被重复计算 S_u 的并集次。

让我们考虑用一种方法容斥掉产生的重复，容易发现连通块也是一棵树，而树满足点数减边数恰好为 1，因此我们令边的贡献为它所连接的两个点同时被覆盖的次数，然后让点的贡献减去边的贡献，就得到了答案。

直接这样做是 O(n^2) 的，但是使用点分治，复杂度即为 O(n\log n)，代码。

类推

此题即讲求在树上选择 k 个连通块使得其并存在一点到所有连通块内的点距离不超过 L 的方案数。

容斥，问题变成对于一点或一边，计算出包含该点的连通块个数，满足连通块内任何一点到达该点的距离不超过 k。

我们知道，对于一棵树，计算包含根的连通块数的简单方法就是按照这个式子 DP：

f(u)=\prod_{v\text{ 是 }u\text{ 的儿子}}(1+f(v))

直接这样暴力是 O(n^2) 的，再结合一些性质就可以拿到出题人自称很良心的 52 分部分分。