[SDOI2017]树点涂色

我们用一个 \(Splay\) 来维护一种颜色，那么第一个操作实际上是 \(access\) 操作。那么每个点的权值就是从他到根节点，经过虚边的数量。

考虑操作 \(2\)，由于我们已经用 \(Splay\) 表示了每一种颜色，所以我们不能再次使用 \(access\) 操作，所以我们要用另一种方式，发现 \(Ans(x, y)=Ans(x, rt) + Ans(y, rt) - 2\times Ans(LCA, rt)+1\)，这个比较显然，所以我们只需要快速计算出一个点的 \(Ans(x, rt)\) 即可，可以采用 \(LCT\) 维护子树的方式，每次修改一条重链就将子树内的权值进行对应加减，这样我们也可以顺便维护操作三了。

[SDOI2017]硬币游戏

假设我们钦定某一轮后的 \(m\) 轮，恰好出现了某个同学所猜测的那样，那么我们在这新的 \(m\) 轮之前游戏必定结束，然后也可能提前结束。

我们设 \(f[i][j]\) 表示第 \(i\) 个人恰好在第 \(j\) 天获胜的概率，设 \(g[i]\) 表示第 \(i\) 天仍然没有一个玩家获胜的概率，再设 \(G(x)=\sum g_ix^i\)，\(F_i(x)=\sum f[i][j]x^j\)。那么我们要求的就是 \(F_i(1)\)。

首先不难发现 \(\sum F_i(1)=1\)，假设在第 \(i\) 轮之后，接下来 \(m\) 轮恰好出现了第 \(j\) 个人所猜的字符，那么如果存在一个人 \(k\) 的某个后缀等于第 \(j\) 个人的某个前缀，那么 \(k\) 就有可能提前于 \(j\) 获胜。可以列出方程：

\[G(x)(\dfrac{1}{2}x)^m=\sum_{k}\sum_{l}[pre(j, l)=nxt(k, l)]F_k(x)(\dfrac{1}{2}x)^{m-l} \]

带入 \(x=1\) 可得 \(G(1)(\dfrac{1}{2})^m=\sum_{k}\sum_{l}[pre(j, l)=nxt(k, l)]F_k(1)(\dfrac{1}{2})^{m-l}\)。所以共有 \(n+1\) 个变量，\(n+1\) 个方程，直接高斯消元即可。

[SDOI2017]苹果树

首先转化题意，由于 \(a_i\) 都大于 \(0\)，不选白不选，所以问题可以等价成：可以免费选择一条链，然后其余部分是树上多重背包。

考虑枚举每一个叶子节点作为免费选择的链的端点时的答案，那么此时树被分成了三个 \(part\)：链上每个点免费选择一个，链上每个点还能选择 \(a_i-1\) 个，其余点满足树形 \(dp\) 的关系。

假设枚举的叶子节点是 \(x\)，考虑到 \(dfs\) 序在 \(x\) 前面的点和在 \(x\) 后面的点是独立的，那么枚举完 \(x\) 之后是一个形如前缀后缀合并的过程，那么我们把第三个 \(part\) 再拆成两个，就是 \(dfs\) 序小于 \(x\) 的和 \(dfs\) 序大于 \(x\) 的。于是整棵树就分成了四个 \(part\)。

第一个 \(part\) 很好计算，第二个 \(part\) 是一个贪心，第三四个 \(part\) 是一个经典的树形 \(dp\)，我们发现第二个和第三四个显得格格不入，但我们可以通过一个巧妙地转化使得不存在第二个 \(part\)：发现树本身的意义是父亲节点至少选择了一个才能选择儿子节点，那么是不是对于一个节点至少选择了一个才能选择其余的呢（废话）。那么我们进行拆点，将一个 \(a_i\) 拆分成 \(1\) 和 \(a_i-1\)，然后 \(a_i-1\) 的点接在 \(1\) 的点下面，发现就把第二个部分归在了三四个部分里面了。

还有一个问题就是第三四个 \(part\) 中，我们需要 \(dp\) 的点并不连续。但是加入我们把 \(dfs\) 序改为出栈顺序，那么链左边的节点的 \(dfs\) 序就是连续的了，同理把邻接表改为从后往前遍历时，仍然采用出栈顺序作为 \(dfs\) 序，那么链右边的点的 \(dfs\) 序就是连续的了。于是我们可以分别对这两个数组进行 \(dp\)，然后将答案合并。

设 \(f[i][j]\) 表示在前缀中考虑到 \(i\) 选择了 \(j\) 个的方案，\(g[i][j]\) 表示在后缀中考虑到 \(i\) 选择了 \(j\) 个的方案。两者转移同理，只考虑 \(f[i][j]\)。如果 \(i\) 点至少选择了一个，那么子树内可以选也可以不选，否则子树内一个都不能选。注意到出栈顺序仍然可以满足一个子树内 \(dfs\) 序连续，因此我们有转移：

\[f[i][j]=max_{k}(f[i-1][j-k]+k\times v_i,f[i-size_i][j]) \]

这个转移是可以采用单调队列来优化的，具体优化方式和多重背包一只，只是加了一个新的 \(f[i-size_i][j]\) 的转移。

[SDOI2018]反回文串

首先考虑一个暴力，考虑每个回文串会对应多少个串。考虑其最短循环节。如果最短循环节为奇数，那么一定是最小循环节本身。如果是偶数，那么前一段可以移动到后面来，所以总方案数是最小循环节长度除以\(2\)

枚举\(N\)的每一个约数，考虑容斥进行计算，每个约数的答案是\(f[x]\)，那么答案应该是\(m^{\lceil\frac{x}{2}\rceil}-\sum_{d|x}f[d]\)

考虑\(m^{\lceil\frac{x}{2}\rceil}\)的意义是至循环至多为\(x\)的方案数，\(f[x]\)表示恰好为\(x\)的方案数，这是一个反演的形式，于是我们可以得出：

\[F(x)=\sum_{k|x}f(k),f(x)=\sum_{k|x}\mu(k)f(\dfrac{x}{k}) \]

所以我们可以得出答案的表达式（\(r(d)=[d\%2==0]\)）：

\[Ans=\sum_{d|n}\dfrac{d}{1+r(d)}\sum_{x|d}\mu(\dfrac{d}{x})F(x) \]

设\(g(d)=\dfrac{d}{1+r(d)}\)

\[Ans=\sum_{x|n}F(x)\sum_{d|\frac{n}{x}}\mu(k)g(kx) \]

我们要想办法将\(g(kx)\)中\(k,x\)分离，也就是要想办法将后面那一坨只和\(\dfrac{n}{x}\)有关系

考虑当\(x\)是奇数，\(k\)是偶数的时候，\(g(xk)\ne kg(x)\)，由于\(x\)为奇数，\(k\)为偶数，考虑到当\(2|\dfrac{n}{x}\)时，那么每一个\(\mu(k)g(kx)\)都有一个\(\mu(2k)\dfrac{g(2kx)}{2}=-\mu(k)g(kx)\)

所以说，\(\sum_{d|\frac{n}{x}}\mu(k)g(kx)\)在\(2|\dfrac{n}{x}\)时恒为\(0\)，所以不等于的情况其实是为\(0\)的。

于是我们可以将\(g(kx)=k\times g(x)\)，也就是说原式可以化简成为：

\[Ans=\sum_{x|n}g(x)F(x)\sum_{d|\frac{n}{x}}\mu(k)k \]

于是我们就要想办法快速计算\(G(x)=\sum_{k|x}\mu(k)k\)，直接枚举每个质因数是否存在即可。

[SDOI2018]荣誉称号

首先可以发现，这个不断除以 \(2\) 向下取整类似于一个树形结构，题意可以转化为树上任意一条长度为 \(k\) 的链，其权值之和均为 \(m\) 的倍数，稍微观察可以发现，任意节点往下走第 \(k\) 层的权值跟他相同，那么唯一可能产生差别的就是前 \(2^k\) 个节点，那么我们只要对这 \(2^k\) 个节点进行 \(dp\) 即可，复杂度 \(O(T2^km^2)\)

[SDOI2019]染色

首先有个暴力 \(dp\)，设 \(dp[i][j][k]\) 表示考虑到第 \(i\) 列，当前列填入的数分别是 \(j, k\)，转移比较显然，复杂度 \(O(NC^2)\)。

发现对于一列，如果已经填入了一个数，那么这一行我们是没有必要存入两维状态的，如果一个数都没有，那么是否可以通过预处理来加速转移呢？

对于每一个已经填入了一个数或者两个数的列，我们记录一个多项式 \(F(x)=\sum f_ix^i\)，其中 \(f_i\) 表示这一列没有填过的数的颜色为 \(i\) 时的方案数。考虑从一个填入了一个颜色的列转移到另一个填入了一个颜色的列是如何转移的，不难发现答案只和这四个数的相同情况有关（也就是可以离散化）。可以发现，在此题中，本质不同的方案只有 \(7\) 种，那么我们分别转移即可。

假设我们是从第 \(i\) 列转移到的第 \(j\) 列，那么枚举第 \(j\) 列那个没有填入的数的取值，然后考虑第 \(i\) 列没有填入的数和已经确定的三个数的相等关系，可以很简单的求出答案。复杂度 \(O(NC)\)。需要对第一列和最后一列进行特判，也就是单独转移一下即可，可以拿到 \(96pts\)。

模拟一下转移可以发现，转移只有全局加，查询，乘；单点加，查询，赋值，可以直接用线段树加速即可获得 \(100pts\)。

[SDOI2019]世界地图

考虑 \(LCT\) 来求 \(MST\) 可以支持动态加边，假设我们求出了每个前缀和每个后缀所对应的 \(LCT\)，那么只需要通过 \((1, m)\) 的边将其合并即可。但这样我们需要可持久化 \(LCT\)，这是不好的。

正解是一个神奇做法。考虑为什么 \(LCT\) 可以支持动态加边，实际上他的操作是每次增加一条边之后，考虑产生的那个环，然后删除环上最大的边。所以在前缀和后缀的合并中，会受到影响的点，只有可能是第一列的点在 \([1, l]\) 构成的 \(MST\) 中，相邻两个节点的路径上的所有边，同理于第 \(m\) 列。

考虑到删除一定是删除环上的最大边权，那么我们建出原图的 \(MST\) 的虚树，边权为虚树路径上权值的最大值即可。

那么我们假设可以构建出 \([1, l]\) 构成的 \(MST\) 所有第一列的点构成的虚树，以及 \([r, m]\) 构成的 \(MST\) 所有第 \(m\) 列的点构成的虚树。那么只需要对连接 \((1, m)\) 的边和虚树上的所有边（不超过 \(3n\) 条边）单独拎出来，跑最小生成树即可。

现在问题是怎么快速找到这些虚树中的所有边，一个无脑的方法是仍然采用 \(LCT\) 进行操作，直接建出虚树（可以用 \(LCT\) 直接求 \(LCA\)）。发现处理前缀 \(MST\) 也可以用处理询问一样的方式，相当于合并 \([1, i-1]\) 和 \([i, i]\) 这两棵最小生成树，那么同样将 \(3n\) 条边做 \(MST\) 算法即可。但是我们实际上同样要维护第一列的点构成的关键点，那么就把第 \(i\) 列和第 \(1\) 列的所有点一起当成关键点一起跑最小生成树即可，每次重新更新一下虚树，将虚树上所有节点代表的边存下来即可。

[SDOI2019]热闹的聚会与尴尬的聚会

由于两问可以重复选择节点，因此我们只需要分别让两者尽可能地大即可。对于第一问，是可以求出符合条件的最大值的。二分答案 \(x\)，然后不断删除度数小于 \(x\) 的节点，直到所有的节点度数都大于等于 \(x\)，最后还剩下点则证明 \(x\) 合法。

第二问是一个经典的 \(NPC\) 问题，可以发现，第一二问答案是一个类似于反比例的增长，可以考虑如下方式来求出极大独立集：随机一个排列，按照顺序加点，如果加入之后满足条件则加入，否则不加入。由于我们只需要让最大独立集大于某个范围而不是最大，所以期望意义下可以得到一个较优解。

[SDOI2019]移动金币

经过漫长的打表，可以发现，一个状态是必胜态，当且仅当差分数组奇数位异或和不为 \(0\)。正难则反，考虑求出等于 \(0\) 的数量，相当于是求有多少组方案，满足 \(m+1\) 个数，奇数位异或和为 \(0\)，且和等于 \(n-m\)。

考虑奇数位偶数位分开计算，对于偶数位，很明显就是一个插板法。对于奇数位，考虑设 \(f[i][j]\) 表示考虑到第 \(i\) 位，和为 \(j\) 的方案数，然后枚举这一位填入多少个 \(1\) 即可，复杂度 \(O(nmlogn)\)，也可以直接 \(FWT\) 做到相同复杂度。