CF2200*树形结构

作者：

CCCkk , 2022-09-06 12:46:07 , 所有人可见 , 阅读 204

Civilization

不难想到用 $dfs/DP$ 求出树的直径，用并查集来维护联通情况，

其中的最优解必然是将两直径的中点相连。

在树上做统计，可以考虑树形 $DP$ ，要求是一个黑色点，可以写状态机来转移。

我们要让重复的路尽量少，求端点为特殊点的直径，并统计直径之外的子树走到被攻击的城市的距离和。

距离和的求法用树形dp就行。我们考虑每一条边的贡献。如果一个点的的儿子的子树内有被攻击的城市，则这条边一定会被走过，答案加2即可。

按位统计即可，比较奇妙的是，可以直接处理每一个二进制位，并分别树上 $DP$ 。

环上的每个点都可以遍历一遍，直接讨论即可，解法很多。

可以用 $set$ 记录以自己为根的节点子树中所有链的长度，自动去重。

我们可以直接从集合中找出 $≤ s - x$ 且为 $k$ 的倍数的数，

用 $set$ 预处理一下加入到集合的数 $u$ ，记录 $u$ 的各个因子。

更优的做法是 $01 trie$

枚举以不同点为最大点时有多少合法方案即可，我们还要对权值相同的情况去重。

等于树上毛毛虫，就是考虑子树，我们要找到它的最大子毛毛虫，以及用来组合的次大子毛毛虫，

然后这些维护的毛毛虫到上面就会有一次竞争，输方就要有点被加入，就是出度 $-1$ ，加一次就好，

最后就是 $f[i][0] + f[i][1] + 2$ ，因为 $f[i][1]$ 会少算，然后之前为了便于转移也会少算。

好题，我们分别考虑子树内和子树外的贡献，

首先我们处理一个数组储存从根开始的距离，

子树内，我们对子树排序，然后再求出子树的前缀和，

这样就可以二分算出答案了，

子树外，可以自底向上用归并求出，然后用二分查找。

从数论分块的基本知识知道除法下取整满足交换律，所以用树剖维护路径乘积，

注意 $y$ 的大小，可以在路径乘积超过 $10^{18}$ 时，直接赋值为 $10^{18}+1$ ，

可以用 $long double$ 维护判断的过程，反正也没啥精度要求。

统计目前节点的子节点的贡献值，更新目前节点的贡献值，同时维护每个节点剩余的权值。

贪心，在子节点的贡献值中取最大的。如果当前节点还有剩余的权值，则在当前节点和其子节点中移动（因为子节点的子节点都遍历完了，无须再往下遍历）