最强跳蚤

By jiry_2，题解By C_SUNSHINE

算法一

显然直接把边权乘起来是不现实的（当然你想写高精度开根我也是兹瓷的），我们考虑每一个质因子$p$，它的次数必须是偶数。

那么我们就有了简单粗暴的算法1：从每个点开始dfs，维护每个质因数的出现次数，预处理每个数的质因数分解即可，复杂度是$O(n^2 \log n)$，空间复杂度$O(w)$。 如果使用map存次数的话，可以做到$O(n \log^2 n)-O(n)$的时空复杂度，期望得分30分。

算法二

我们把$w$质因数分解，每个出现过的质数离散化一下，可以发现至多出现$O(n \log n)$个不同的质数（事实上当$w/n$不是很大的时候这个数目是$O(n)$的）。

那么使用bitset维护每个质数的出现次数，再dfs就可以做到$O(\frac {n^3} {32})$了，但是这样并不能跑出$n=3000$，事实上我们直接对离散化之后的质数开桶统计就能做到$O(n^2 \log n)$了，期望得分50分。

算法三

对于$w \leq 80$的数据，由于80以内的质数不超过32个，我们可以对第$i$个质数分配一个权值$2^{i-1}$，一条边的权值就是$w$所有质因子的权值的异或，一条路径的权值就是每条边权值的异或，从根开始dfs求出根到每个节点的权值，那么$u \rightarrow v$是可行的当且仅当根到$u$的权值等于根到$v$的权值，把根到所有节点的权值排序统计一下即可。

时间复杂度$O(n \log n)$。

算法四

考虑推广算法三，其实我们可以对于每个质数，给它分配一个$[0,2^{64})$内的随机数，于是一条合法路径权值一定是$0$，而不合法路径只有$\frac{1}{2^{64}}$是$0$，这个概率可以忽略不计。剩下的按照算法4将根到每个节点的权值排序统计即可。

至于质因数分解，可以预处理$10^4$以内的质数表，然后每次暴力分解，复杂度是$O(\sqrt{w} + n \pi (\sqrt{w}))$，可以通过全部测试点。

人类补完计划

By matthew99，题解By C_SUNSHINE

算法一

对于$m \leq 20$的情况，我们可以暴力枚举每条边在不在$S_v$里，并判断是否符合题目要求，把合法的方案的权值加入答案中。

时间复杂度$O\left(m2^m\right)$，期望得分5分。

注意到不同的连通块之间的贡献独立，对每个连通块分别处理，可以通过第二个测试点得到10分。

算法二

观察题意其实就是枚举所有的基环外向树，$w$是非叶节点个数，把$2^w$加入答案。

那么我们首先考虑基环外向树的计数，第一步是环的计数。 环的计数可以非常容易的通过状态压缩DP来实现设$cir_{i,S}$表示集合$S$组成一条以$j$开头$i$结尾的链的方案数（令$j$为$S$中编号最小的元素）， 转移时枚举$i$的下一个元素即可，要求和$i$直接有边且编号$>j$，最后对于每对$i,S$，若$i,j$之间由有边，则将$cir_{i,S}$加入集合$S$的答案$f_S$中。 注意一个环从$j$开始有两种不同的顺序遍历，所以最后答案要除以$2$。

接下来考虑集合$V$组成的基环外向树计数$cnt_V$，我们可以枚举环的集合$S$，然后把环缩成点，直接套用Matrix-Tree定理即可，这样处理所有$V$的总复杂度是$O\left(3^n n^3\right)$的。

我们考虑给权值一个意义，假设每个节点可以染成黑白两种颜色，叶子节点只能染成白色，那么只要计算染色的总方案数，一个$S_e$就会被恰好计算$2^w$次。

对于染色方案数的计算，我们可以考虑容斥原理，用总方案数减去存在黑色叶子节点的方案数，注意到基环外向树删去叶子之后仍然是基环外向树。

令$val_V = 2^{|V|}cnt_V$，枚举叶子节点集合$T$，则方案数

$$g_V = \sum_{T \subset V,T \neq \emptyset} \ (-1)^{|T|} \times val_{V-T} \times ways(T,V-T)$$

其中$ways(T,S)$表示$T$向$S$连边的方案数，为$T$中所有节点在$S$中邻接点个数之积，容斥时暴力计算就好，这部分时间复杂度是$O\left(3^n n\right)$的。

于是这个算法总的复杂度就是$O\left(3^n n^3 \right)$，期望得分30分。

算法三

算法2的时间复杂度瓶颈在与求$cnt_V$上，我们考虑换一种计数方式，把$cnt_V$的计算和答案的计算放在一起。

首先考虑$V$集合的权值和计算，对于$V$的每一个子集$T$，我们都计算出叶子节点集合为$T$的基环外向树个数$g_T$，那么权值和就可以直接计算了。

依旧使用容斥原理，令$h_T = cnt_{V-T} ways(T,V-T)$，即$T$为叶子节点集合的子集的方案数，然后对$h$做子集反演得到$g$：

$$ g_S =h_S + \sum_{S \subset T} (-1)^{|T|-|S|} \times h_T $$

那么显然$V$集合对答案的贡献就是$2^{|V|}f_V+\sum_{S \subset V,S \neq \emptyset}\ \ 2^{|V|-|S|} \times g_S$。

接下来考虑$cnt_V$如何计算，对于每个$V$首先把单独为一个环的情况$f_V$加入答案， 然后既然我们已经求出了以任意集合$S$为叶子的基环外向树方案数$g_S$，直接把$cnt_V$加上所有$g_S$的和即可。

计算$h_T$的总复杂度是$O\left(3^n n\right)$的，子集反演可以使用$O\left(2^n n\right)$的快速算法，总复杂度也是$O\left(3^n n\right)$，期望得分70分。

算法四

我们采用一种新的思考方式，考虑树的prufer编码，每次选取最小的一个叶子删去并将其邻接点加入prufer序列。

具体令$dp_{V,S}$表示$V$集合组成的$S$不能为叶子的基环外向树数目。

转移时我们令$k$为$V-S$中编号最小的节点，我们有两种转移方式：

1.令$k$为叶子，并将$k$删去，那么我们在$k$的邻接点中选取一个节点$l$，将$l$设置为可以为叶子。

2.将$k$设置为不可为叶子。

当$V=S$时可以发现答案一定为一个环，即$dp_{V,S}=f_V$。

注意到这样的统计会有重复计数，因为对于一个基环外向树，令其点集为$V'$，非叶节点集合为$S'$，那么对于所有$V=V',S \subseteq S'$都会被$dp_{V,S}$计数一次， 共会被计数$2^{|S'|}$次，我们发现这恰好就是这个基环外向树的权值，那么对所有的$dp_{V,S}$求和即可。

时间复杂度也是$O\left(3^n n\right)$，期望得分70分。

算法五

考虑对算法2进行优化，算法2的瓶颈在于计算集合$V$构成的环套树的方案数，而这个方案数在算法3中我们可以枚举叶子节点的集合进行容斥，而算法3的瓶颈在于莫比乌斯反演。

我们考虑把算法2和算法3结合起来，我们直接枚举非叶节点集合$S$，在枚举$S$的超集$V$，枚举$V$可以使用dfs，在dfs的过程中计算$ways(V-S,S)$，使用如下容斥式子计算答案：

$$g_V = \sum_{S \subset V} (-1)^{|V|-|S|} \times val_S \times ways(V-S,S)$$

dfs之后统计$S$对于$V$的贡献即可，复杂度是$2^{n-|S|}$的，总复杂度就是$O\left(3^n\right)$了，期望得分100分。

matthew99的计数小课堂

大家好这里是matthew99，我来说一些更好的求每个子集组成的基环外向树的方法：

我们注意到算法二有一个很不优美的地方，为了求出每个子集的基环外向树个数，我们不得不使用了一个$O(3 ^ n n ^ 3)$的算法。后面的算法中给出了更好的求这个的办法，但我这里要扯一些其他的办法。

注意到我们如果求出每个点集中恰有$0, 1, 2, \cdots n$条边的连通图个数，那么我们就能求出每个子集的基环外向树个数，这个很容易用容斥得到。考虑记录每个点集边数为每一个值的任意图个数和连通图个数，我们用经典的思路，枚举$1$号点所在连通块是哪些点，然后再枚举这个连通块内的边数然后直接容斥即可，这样复杂度是$O(3 ^ n n ^ 2)$，期望得分50分。我们如果用二维集合占位多项式并实现对一个二元函数求$\ln$，我们可以将这一部分做到$O(2 ^ n n ^ 4)$，但其实际效率甚至不如直接容斥。

还有一个思路就是我们考虑有向图中的基环外向树可以看成就是每一个点恰好连出去一条边，无向图我们可以定向之后达到同样的效果。考虑记录每个子集，每个点恰好指定一条边连出去的图的个数，答案似乎是度数的乘积，这样我们似乎考虑直接套用前面所述的容斥算法就可以做到$O(3 ^ n)$了，但其实不然，由于是无向图我们可能会出现重边，但是我们注意到如果有重边，相当于一棵树上随便找一条边让它再被选一次，所以我们用Matrix-Tree定理$O(2 ^ n n ^ 3)$求出每个子集的生成树个数，然后在此基础上很容易实现$O(3 ^ n)$的容斥算法求每一个子集的基环外向树个数。

思考熊

By jiry_2

QAQ 这题的来源是我在做乐滋滋胡策的时候 YY 出的一个 idea，那个时候觉得这个 idea 还是挺厉害的，于是就接了这么一个 C 题的坑。

但是用 idea 造题这种事情毕竟不靠谱，在造题的过程中发生了各种各样的偏差..在经过了各种各样的挣扎之后，出出来这么一个题，有很多的不足之处 QAQ 求轻喷。

算法一

在询问时暴力枚举每一个可以使用的接应点，算出路径的权值和并更新答案。在计算路径的权值的过程中，需要计算两个点之间的 LCA。

如果直接使用倍增或者树剖计算，那么时间复杂度是 $O(nm \log n)$，期望得分 $7$ 分。

可以发现两个节点的 LCA，就是在欧拉序中，它们第一次出现的位置之间深度最小的节点。于是就可以用 ST 表来询问两个点之间的 LCA 。这样时间复杂度是 $O(nm)$，期望得分 $20$ 分。

算法二

如果只有插入的话，我们可以直接分块。在插入的过程中，一旦插满一块，我们就对每一个树节点预处理出到这个块中所有节点的距离的最大值，这是一个经典的树形 DP 的问题，我们可以在 $O(n)$ 的时间内求出答案。

在询问的时候，对于询问区间内完整的块，可以直接得到答案；对于块外的块，使用算法一中单次 $O(1)$ 的算法计算权值。这样的时间复杂度和空间复杂度都是 $O(n \sqrt n)$ 的。

那么现在问题来了，有删除的时候怎么办呢..有一种非常简单的方法就是不管..这样可以通过第三个 subtask，期望得分 $40$ 分。

肛道理

可能到这儿有人会说，出题人你会不会造数据，又偏题出出暴力放放..那么我们来肛道理..

如果知道了块的大小，卡这个做法是非常轻易的——只要在刚好插满一个块的时候反复重复插入和删除，这样时间复杂度就边 $O(n^2)$ 了。

但是问题来了..作为出题人，我根本不知道泥萌的块大小是多少 QAQ

在比赛的时候对着程序卡是一种可行的方案，但是我对着程序卡同样会被婊 QAQ 再加上如果写程序的时候加点奇技淫巧，比如拿输入数据 srand 一波然后随一个块大小出来，这样我即使是对着程序也卡不掉了..

所以最后想想索性都不卡了，因为如果我对着固定块长的卡了，却放了随机块长的过了，大家都不高兴是吧..反正只是暴力分嘛是吧..放过去了就放过去了..

难道就没有什么不存在被卡可能性的算法吗？难道就没有什么能卡这个的方法吗？当然都是有的..在后面会讲..

算法三

考虑 $w \geq 0$ 的部分分，我们来考虑一下如何快速求一个点到一个点集 $S$ 的距离的最大值。

我们可以发现，假设 $S$ 中距离最远的一对点是 $u$ 和 $v$，那么任意一个点 $x$ 到点集 $S$ 中的点的距离的最大值一定是 $x$ 到 $u$ 的距离或 $x$ 到 $v$ 的距离，证明还是很显然的。所以我们就可以使用两个点来代替一个点集。

我们可以使用线段树，对线段树的每一个节点来维护这个区间中的点集的信息。合并两个点集的信息时候，我们可以把这两个最远点对一共四个点放到一起，那么它们两两之间距离最远的一对点就是合并后点集中距离最远的两个点。可以合并信息，那么插入和删除操作就可以轻易地完成。

在询问答案的时候，只需要对定位出来的每一个子区间统计计算答案并更新就好了。

时间复杂度 $O(n \log n)$，可以通过第五个 subtask。

算法四

当 $w$ 可以小于 $0$ 时，维护直径的方法就不行了。

如果点集 $S$ 给定，我们可以先求出点集 $S$ 在树上的虚树，然后求出虚树上每一个点到它的子树中的关键点的最远距离 $d_i$ 和到子树外的关键点的最远距离 $u_i$ ，这个可以用两遍 DFS 预处理来解决。

现在要询问点 $x$ 到点集 $S$ 中的点的最远距离，我们可以先找到 $x$ 深度最大的祖先 $f$，使得 $f$ 在虚树的某一条边上，接着我们找到 $f$ 所在边的深度较深的端点 $v$，那么答案就是 $\max(dis(x,v)+d_v, w_x-w_v+u_v)$，其中 $dis(x,v)$ 表示两点之间的距离，$w_v$ 表示 $v$ 到根路径上所有边的权值和。

那么如何找到 $f$ 呢，我们可以在虚树中找到 DFS 序小于等于 $x$ 的最后一个节点 $l$ 以及大于 $x$ 的第一个节点 $r$（这个可以通过一次二分解决），那么 $f$ 就是 $x$ 和 $l,r$ 的最近公共祖先中深度较深的那个（这个可以通过脑补虚树的构建过程得到）。在找到 $f$ 后，我们二分出虚树中 DFS 序大于等于 $f$ 的第一个节点，那个就是 $v$ 了。

这个做法需要两次二分和两次 LCA，如果大家有更好的定位方法欢迎来和我讨论。

至于修改，我们先来考虑插入：在只有插入的时候我们可以使用二进制分组来解决。

我们可以对最普通的二进制分组算法进行一点拓展来支持区间查询操作：在把两个块合并成一个新块的时候，保留原来两个块，并把新块作为原来两个块的父亲，这样我们就得到了一个线段树结构。这样在查询的时候，就可以和线段树一样，先找到完整组成询问区间的 $O(\log n)$ 个块，然后分别在块中查询。

这样我们就把一个动态插入的问题转化成了静态的问题，时间复杂度 $O(n \log^2 n)$，空间复杂度 $O(n \log n)$，可以通过第四个 subtask。

算法五

最后我们来考虑删除操作，出这题的时候，核心在于一种将二进制分组拓展使得它可以在时间空间复杂度不变的情况下支持删除，这个虚树的背景只是我们为了找一道“只能用二进制分组做的题”的时候，硬套上去的。

普通的二进制分组之所以不能支持删除，是因为它的复杂度是均摊的，我们在它重建的时候，可以通过不停的删除和插入，使得它不停地合并一些非常大的块。

我们观察拓展后的二进制分组结构，它有 $t$ 层，从下到上第 $i$ 层的每一个块中有 $2^i$ 个节点。在原来的二进制分组中，我们相当于在每一个块插满后，立即重建这个块。

现在我们来考虑这个一个做法，在删除的时候，我们给所有涉及到的块（最右边一列）打上狗带标记，表示这个块的信息目前不对。在查询的时候，如果我们当前查询的块是狗带的，那么就递归对它的两个孩子进行求解。

当我们插满一个块的时候，我们不立即重建这个块，我们访问它的前驱块（同一层中相邻的前面那个块），如果它的前驱块是狗带的，就重建前驱块，否则就什么都不干。

接着我们来分析这个算法的复杂度。在这个算法中，我们相当于每时每刻都保证了每一层至多有一个块是狗带的，因此在查询的过程中，我们只会对 $O(\log n)$ 个块进行递归，因此需要查询的块的个数还是 $O(\log n)$ 的，于是查询复杂度还是 $O(\log^2 n)$。

接着我们对第 $i$ 层计算重建的代价，考虑这样两个事件：

1. 给一个块打上标记，这个事件复杂度是 $O(1)$ 的。
2. 重建一个块，这个事件的复杂度是 $O(i 2^i)$ 的。

令 $n$ 为序列长度，$len_i$ 为第 $i$ 层没有被打标记的块的总长度，令势能函数 $\phi (i)=|n-len_i-2^i|$。一次插入或者删除至多让势能函数增加 $1$，而一次事件会让势能函数减少 $2^i$，于是可以得到第 $i$ 层的均摊复杂度是 $O(ni)$。

让 $i$ 在 $1$ 到 $O(\log n)$ 范围内求和，那么就可以得到它的时间复杂度是 $O(n \log^2 n)$ 的。

因此这个算法的总时间复杂度是 $O(n \log^2 n)$，空间复杂度是 $O(n \log n)$。

算法二中，我们也可以一样，在分块的时候延迟重构，保证至多有一个块的信息是狗带的，这样时间复杂度就对了。

这就是这个算法的全貌了，当初在脑补出这题的时候感觉还是非常厉害的，但是在造数据的时候发现：根本没法卡暴力。

实际上面临的问题和算法二一样，如果选手在二进制分组的时候随机扰动一下，让出题人不知道你的代码的重构的位置，那么就没法卡了，实际上在期望情况下随机分组的复杂度的确是对的。

在这题的数据中，我对一些比较正常的重构位置附近卡了一下，而如果你在非常奇怪的地方分组的话，算法的常数会变得非常大，感觉随机分组的方法还是比较难通过的。

当然，硬要卡的话，这种随机分块和随机分组的方法还是可以卡的。我们可以用交互的形式，你的代码边运行，我的交互库边生成数据，发现你这几个操作特别慢，就赶紧删除回去再来一遍。

然而交互题实在是太麻烦了..要改成交互的话，我必须在交互库里内嵌标程，而交互库又必须要写 C 和 Pascal 的...

于是只能选择狗带了QAAAAAQ

算法六

当然..上面这些算法基本没有最开始那棵树什么事..实际上在出题的时候我们也没怎么考虑那棵树..

本来想用凸包做这题的内容的，但是乐滋滋的胡策里已经有凸包了，后来又想用半平面交，但是半平面交和凸包又没有什么区别。再后来想用 mex，但是 mex 的题实在太多了，又不是很好。于是最后想了想发现虚树这玩意不是很好合并，决定就是它了。

然而在考前 10min 我突然发现好像可以在那棵树上直接做 QAQ 根本不关二进制分组什么事.. 感觉成功身败名裂了。

我们可以直接对最开始的树点分治，对每一层分治维护分治中心的的子树中的最远点（要维护最远点和扣除最远点所在子树后的最远点），这可以用线段树或者平衡树随便搞..

然后..就做完了..

当然实际上要过这题也没有这么轻易..平衡树常数太大估计会 T，而最裸的线段树因为我们不知道值域，需要动态开节点，所以空间是 $O(n \log^2 n )$ 的，这肯定是过不了的。

但是我们可以用一些鬼畜技巧来优化掉空间的一个 $\log n$：对每一个节点，我们先规定它的线段树的值域为 $2^0$，然后在插满的时候，把值域修改为 $2^1$，然后暴力重构线段树并分配空间，再插满就修改成 $2^2$...

脑补一下就发现空间 duang 的一下变成 $O(n \log n)$ 了。

当然这样空间的常数比较大，具体能不能过这道题我不知道，这一块里的算法我也没有真正写过，都是我瞎 BB 的..（但是这样也已经掩盖不了这是一道垃圾题的事实了）

感觉出数据结构题实在太难了 QAQ 还是小清新计数题好..

这道题就当做是对一些奇技淫巧的推广吧..对我这种写不动数据结构的老年人来说这种方法还是挺 work 的，都是一些公式化的东西，也挺好写..

不过现在的科技这么发达，真正想要出又要新颖，又要只能用这种方法做的题目真的是太难了 QAQ

惨啊..