[ZJOI2015]地震后的幻想乡

考虑克鲁什卡尔的算法流程，发现最小生成树之和相对大小关系相关，由于是实数期望，所以可以忽略掉大小关系相等的情况。一种简单的方法就是枚举 \(m\) 条边的相对大小关系，然后模拟克鲁什卡尔算法，假设在第 \(i\) 条边加入时联通，那么答案为 \(\dfrac{i}{m+1}\)，因此设 \(f_i\) 表示加入 \(i\) 条边时仍然没有联通的方案数，那么答案为 \(\dfrac{1}{m+1}\sum \dfrac{a_i}{\binom{m}{i}}\)。因此只需要快速求出 \(a_i\) 即可。

设 \(f[i][j]\) 表示集合 \(i\) 中连接了 \(j\) 条边，联通的方案数，那么 \(a_i=1-f[M][i]\)。接下来就是常规操作了，固定最小的点 \(p\) 必须被包含，那么 \(f[S][i] = 1-\sum_{T\in S, 2^p\in T}f[T][j]\times \dbinom{cnt_{T\&S}}{i-j}\)，直接转移即可，复杂度 \(O(3^n\times m)\)，当然可以采用子集卷积进行优化，但是实际效率可能会更慢。

[ZJOI2016]大森林

查询操作可以在修改之后统一完成，我们只要能还原出最后的每一棵树即可。然后相邻的两棵树的关系一定是十分密切的，考虑依次枚举每一棵树，然后还原出当前这棵树。

我们从 \(1\to n\) 枚举每一棵树，然后可以发现只有 \(4\) 种操作：删除一个操作 \(0\)，增加一个操作 \(0\)，删除一个操作 \(1\)，增加一个操作 \(1\)。

对于操作 \(0\)，实际上把每个操作 \(0\) 当成 \([1, n]\) 也没有问题，因为操作 \(1, 2\) 都不会操作不存在的点。只需要在操作 \(1\) 的时候判断其合法性即可，由于每次操作都是一段区间，所以可以将删除/加入一个 \(0\) 操作看成删除/加入一些 \(1\) 操作，由于总量是 \(O(M)\) 级别的，所以只需要处理 \(1\) 操作即可。

考虑两次操作 \(0\) 之间的所有修改操作，他们都是一类点，我们可以建一个虚点，然后每次增加或者删除 \(1\) 操作就是直接将虚点的父亲改掉即可。然后我们用一个点存储他到父亲节点的边是否存在，注意这里不能直接 \(spilt\)，需要求出 \(LCA\)，然后统计 \(dep\)，\(LCA\) 即先 \(access(x)\) 之后再 \(access(y)\) 第一个通往 \(x\) 的那个点。

[ZJOI2016]小星星

先考虑一个暴力，考虑这是一棵树，我们考虑树形\(Dp\)，直观的想法是设\(dp[i][j][k]\)表示考虑到以\(i\)为根的子树，在图中映射出来的点集为\(j\)，且当前\(i\)号点所映射的点为\(k\)的方案数。转移比较显然，对于每个\(u\)，枚举一个子树内选择的点的子集即可。这里的复杂度是\(O(3^NN^3)\)的，\(N^3\)分别来自枚举根节点，枚举根节点和子树分别选择什么，可以通过\(FWT\)优化到\(O(2^N N^4)\)，还不能通过此题。

考虑到\(i, k\)是省不掉的，而且这个范围也不难猜到复杂度跟\(O(2^N)\)有关，我们尝试优化掉\(j\)这一维。

我们需要保证每个点恰好需要用一次，才导致于我们必须要记录 \(j\) 这一维，那如果不限制这个，可以任意选择呢？可以发现，我们 \(2^n\) 枚举所有子集，强制规定树上的映射只能选择这个子集内的点，发现 \(j\) 这一维突然消失了，然后所求得的答案对最终答案的贡献就是\((-1)^{n-|S|}\)。于是我们的复杂度就变成了\(O(N^3\times 2^N)\)，由于我们只能选择一个子集，大概可以带一个\(\dfrac{1}{4}\)的常数，于是我们可以通过此题。

[ZJOI2016]旅行者

考虑分治，假设当前分治矩形长宽分别为 \(a\times b\)，且 \(a>b\)，那么我们将其分成两个矩形，大小为 \(\dfrac{a}{2}\times b\)。然后求出边界上每个点到其他所有点的最短路，对于一个询问，如果其两个点都在其中一个矩形中或者分在了两个矩形中，那么就更新一下答案，不难计算复杂度为 \(O((S+Q)\sqrt{S}logS)\)。

[ZJOI2017]线段树

找到 \([l, l]\) 与 \([r, r]\) 的 \(LCA\)，抛开这一层，暴力递归到下一层去，然后将询问拆分成 \([l, x], [x+1, r]\)，那么询问就变成了一个区间的前缀或者后缀。不妨只考虑前缀，后缀也可以用类似的方法进行求解。

考虑求出 \([r, r]\) 与 \(u\) 的 \(LCA\)，简单画图+分类讨论可以得出，我们只需要支持查询 \([l, r]\) 的节点个数即可求出答案，很显然只需要深度做差即可。

[ZJOI2017]仙人掌

题意可以转化成：给定一棵树，有一些已经选择的链，你再选择若干条长度大于 \(2\) 的链，使得其没有公共边。然后不难发现，只要去掉所有的环，那么原图会变成一个森林，森林之间互不影响，求出每个数的答案相乘即为答案，所以我们只需要可以计算出树的答案即可。

考虑怎么计算一颗树的方案数，有一个神奇的转化：考虑一个合法的方案，我们把所有的非环上的边看成一条重边，也就是一个环，那么原问题可以转化成：给定一棵树，求有多少种方案，选择若干条链覆盖所有边，且所有链边互不相交。为什么是对的呢？环的长度一定大于等于三，而没有被覆盖的边如果把他看成长度为 \(2\) 的环，那么所有的边都会被恰好覆盖一次，且我们对链而的长度没有了限制！

考虑转化题意要怎么进行计算，先把所有的边看成是一条链，那么对于每个点，他可以选择连接两条链，也可以不连接，我们设其度数为 \(d_i\)，设 \(f_i\) 表示 \(i\) 叶子结点的菊花图的答案，那么根据乘法原理，答案为 \(\prod f[d[i]]\)，至于 \(f_i\) 的计算，枚举其是否匹配，易得 \(f_i=f_{i-1}+f_{i-2}\times (i-1)\)。

[ZJOI2017]树状数组

首先题意可以转化成：给一段区间的一个数等概率异或一，查询两个点相等的概率。

不难想到，我们可以将区间分为三类：只包含第一个点的，只包含第二个点的，包含两个点的。其余区间对答案没有影响。

可以先考虑一个暴力 \(dp\)，设 \(dp[i][0/1]\) 表示考虑到第 \(i\) 次修改，当前节点是 \(0/1\) 的概率，然后转移比较显然，只和区间长度相关。如果我们将一个区间的左右端点 \((l, r)\) 看成二维平面上的一个点，那么我们对答案有影响的三类区间分别在三个矩形中，那么我们只需要快速维护矩形的 \(dp\) 值即可。可以用 \(KDT\) 来实现，每个节点存的是只考虑这个节点所包含的点的 \(dp\) 值。

[ZJOI2018]历史

首先对于每个点分开考虑，这个点对答案的贡献考虑怎么计算。

首先每个点的每一个儿子的子树，对根节点的贡献是一样的。所以，每一个点对答案的贡献只跟：当前点的\(a_i\)以及所有儿子的子树\(a_i\)之和有关

假设所有有关的值的最大值为\(Ma\)，和为\(Sz\)，那么这个点对答案的贡献是：\(Sz-max(0, 2\times Ma-Sz-1)-1\)（-1是因为最开始占领需要花费一次）。\(Sz-1\)很好维护，所以我们现在只需要考虑怎么维护\(max(0, 2\times Ma-Sz-1)\)

以下是神仙操作：

考虑两种情况对答案的贡献，第一种情况是\(2\times Ma \ge Sz+1\)，发现这种\(Ma\)最多只有一个。于是我们可以类似\(LCT\)，把所有满足这个条件的点和其父亲连重边，其余连轻边，不难发现仍然满足\(LCT\)的性质。

考虑每一次修改，我们对其路径上的点进行修改，重链修改的部分只有可能是把路径上的一条轻链变成重链。这样的修改最多是\(log\)个，暴力修改即可

[ZJOI2019]语言

考虑一个点可以到达的点一定是以下方式构成：考虑所有经过他的链，然后这些链的端点所形成的连通块，即为一个点所有可以到达的点。假设求出了这些点，可以通过建立虚树的方式求出连通块大小。

考虑具体的计算方式，将所有关键点按照 \(dfs\) 序排序，每个关键点对答案的贡献为他到上一个关键点的 \(LCA\) 的距离，因此我们可以很方便的支持插入/删除一个关键节点。

考虑一个点 \(u\) 的所有关键点和儿子节点的所有关键点之间的关系，不难发现就是先取并集，然后加上起点在点 \(u\) 的点，计算答案之后，减去起点和终点均在 \(u\) 子树内的链（也就是 \(LCA\) 为 \(u\) 的链），再合并上去，用启发式合并可以简单做到 \(O(Nlog^2N)\)

[ZJOI2019]开关

设\(f_i\)表示状态为\(i\)的期望步数，那么我们考虑转移方程：

\[f_i=\sum_{k}f_{i\oplus 2^k}\times p_{k}+1=\sum_{j\oplus k=i}f_{j}\times p_{k}+1 \]

其中\(p_{k}\)只在\(2^k\)处为\(p_k\)，其余部分为\(0\)。

然后我们可以利用高斯消元来求解，复杂度\(O(8^n)\)，我们还需要进行优化。

考虑设\(F(x)=\sum_{i=0}^{n}f_ix^i, G(x)=\sum_{i=2^k}p_kx^i, I(x)=\sum_{i}x^i\)。所以我们可以写成：\(F(x)=F(x)\times G(x)+I(x)+c\)，其中\(+c\)的意义是强制把\(f_0\)转成\(0\)。

接下来是一步神奇的操作，这里实际上是一个异或卷积，我们可以把它们强行转成点值，于是我们有：\(FWT_i(F(x))=FWT_i(F(x))\times FWT_i(G(x))+FWT_i(I(x))+FWT_i(c), FWT_i(F(x))(1-FWT_i(G(x)))=FWT_i(I(x))+FWT_i(c)\)。不难发现这些点值都很有规律。

\(1.FWT(C)\)

不难发现他恒等于\(c\)。

\(2.FWT_i(I(x))\)

设\(i\)有\(k\)个\(1\)，考虑\(FWT_i=\sum_{j}(-1)^{|i\&j|}=2^{n-k}\sum_{j=0}^k\dbinom{k}{j}(-1)^j=2^{n-k}[k==0]\)。

\(3.FWT_i(G(x))\)

\(FWT_i(G(x))=\sum_{j}(-1)^{|i\&j|}\)，也就是所有\(0\)位置上的\(p_j\)之和减去\(1\)位置上的\(p_j\)之和。

当\(i=0\)时，\(FWT_i(G(x))=1\)，所以此时\(-FWT_i(I(x))=FWT_i(c)\)，所以我们解出\(c=-2^n\)。

我们先考虑\(i=0\)。\(i=0\)时上面的方程不能计算，但由于\(IFWT_0(FWT_0(F(x)))=0\)，所以\(FWT_0(FWT_0(F(x)))=0\)，即\(FWT_0(F(x))=-\sum_{i\ne 0}{FWT_i(F(x))}\)，算出所有的\(FWT_i(F(x))\)之和即可。

\[FWT_i(F(x))=\dfrac{-2^n}{1-FWT_i(G(x))}=\dfrac{-2^n}{2\times \sum_{i\&{2^k}\ne 0}p_k} \]

\[\begin{aligned}&\;\;\;\;IFWT_i(FWT_i(F(x)))\\&=\dfrac{1}{2^n}\Big(\sum_{j\ne 0}(-1)^{|i\&j|}\dfrac{-2^n}{2\times \sum_{i\&{2^k}\ne 0}p_k}+\sum_{j\ne 0}\dfrac{2^n}{2\times \sum_{i\&{2^k}\ne 0}p_k}\Big)\\&=\Big(\sum_{j}\dfrac{|i\&j|≡1\;mod\;2}{\sum_{i\&{2^k}\ne 0}p_k})\end{aligned} \]

到这里我们已经有一个\(O(2^n)\)的做法了，考虑怎么加速这个计算过程：设\(dp[i][0/1][j]\)表示考虑了前\(i\)个数，和\(S\)集合的交集的奇偶性为\(0/1\)，当前的\(p_i\)之和为\(k\)的方案数。直接转移即可，复杂度\(O(n\sum P)\)。