RainAir
My OI Blog
RainAir
「CF599E」Sandy and Nuts

题意

给你若干限制,限制为 $lca(u,v) = c$ 和 $(u,v)$ 有连边,数一下以一为根的满足限制的树的个数。
$n \leq 13$,限制总数 $\leq 100$

题解

这个题目太神仙了。。远古 CF 场的题目还是好。
考虑设 $f_{v,S}$ 表示 $v$ 节点子树内的点是 $S$ 的树的个数。答案是 $f_{0,U}$ (将点的标号减一后)
首先我们考虑一下不考虑限制怎么转移:一个 naive 的想法是:
$$f_{v,S} = \sum_{T \subseteq S} \sum_{x \in T} f_{x,T}* f_{v,S-T}$$
也就是枚举这次将那些点拿下去建一个子树。
但是我们考虑到会重复:我们考虑子树内的点集 $\{1,2,3,4,5\}$ 如果这样统计,那么方案 $\{1,2\} \{3,4,5\}$ 和 $\{3,4,5\} \{1,2\}$ 都会被计入,但是显然这两种方案是应该被计入一次的。
于是我们考虑固定 $T$ 内的一个点,这样就不会出现上面的情况了。
接下来我们来考虑限制,我们其实只需要转移的时候排除掉所有不正确的情况就好了:
1. lca(u,v) = c
– 考虑如果你现在枚举的这个点为 $c$ 但是 $u,v$ 都在一个子树中,这显然不行。
– 考虑如果 $c$ 在你枚举的这个子树,那么 $u,v$ 也必须在这个子树中
2. $u,v$ 有一条边
– 如果这个边的一个端点在你现在枚举的点上,那么另一端点只能有至多一个点在这个子树中,并且如果这个点在子树中,需要强制这个点为子树的根。
– 如果端点不在你枚举的点上,$u,v$ 只能同属于这个子树或同不属于这个子树。

然后分类讨论一下就做完了https://blog.aor.sd.cn/wp-content/uploads/2019/10/QQ20191011-112317.png

赞赏
知识共享许可协议
本文链接: https://blog.aor.sd.cn/archives/862
如文中无特殊声明,本文采用 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

「CF599E」Sandy and Nuts
题意 给你若干限制,限制为 $lca(u,v) = c$ 和 $(u,v)$ 有连边,数一下以一为根的满足限制的树的个数。 $n \leq 13$,限制总数 $\leq 100$ 题解 这个题目太神仙了。。远古 CF 场的题目…
扫描二维码继续阅读
2019-10-11
标签
近期评论