Luogu6799 「StOI-2」独立集

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

题意 ：给出一棵 个节点的树与 条路径（定义为点的集合），问这些路径组成的独立集方案数。

答案对 取模。

，时限 。

先考虑链上的子问题。

将所有区间按照终止点从小到大排序，设 为节点 中的独立集方案数。

对于每一个区间 ，都有 。

也可以不选择任何路径，于是 。

上树之后，按照路径最浅点（LCA） 的深度从大到小排序处理。

设 为 子树内的独立集方案数。

在 点，若不选择任何 LCA 为 的路径， 加上各个儿子的 的乘积。

若选择（满足 的）路径 ，则方案数为 路径上所有分支子树方案数的乘积，如下图红色部分所示：

考虑维护 表示 所有儿子的 的乘积，查询 的 的乘积，再除去 部分的乘积（它们恰好被算重一次）

但是，可能构造出 使得除法无法进行，考虑如何规避除法。

不难发现，在灰色路径中， 缺失了两个儿子， 没有缺失儿子，其余部分缺失一个儿子。

（特判 其中一个等于 的特殊情况）

对于点 和若干直接儿子 ，令 ，即缺失该儿子的乘积。

不缺儿子的情况直接乘 即可。

这样，设 是 路径上的倒数第二个点，只需查询 的 积，即可处理只缺一个儿子的情况。

对于缺两个的情况，使用一棵额外的线段树维护区间积即可。

维护 时需要支持快速求树上路径积，以及从深至浅的修改。

可以转化为子树乘和单点查询，使用线段树即可做到 。