联赛真题LIST

本 $\texttt{LIST}$ 用于记录联赛经典题。

不过应该会咕得比较厉害

[CSP-S 2019]树的重心

给一棵树，令 $p_i$ 为删去树上一条边后，$i$ 是分裂出两棵树中某一棵的重心的次数。求 $\sum_{i=1}^n i \times p_i$。

$n \le 3 \times 10^5$

首先拿出一个原树重心做根，令一个非根的点 $x$ 子树大小为 $siz_x$，重儿子的 $siz$ 为 $maxson_x$。若要使 $x$ 是某一棵分裂出的树的重心，另一棵的大小为 $S$，那么有：

$$maxson_x \times 2 \le n - S$$

$$(n - S - siz_x) \times 2 \le n - S$$

化简得：

$$n - siz_x \times 2 \le S \le n - maxson_x \times 2$$

并且显然这条删去的边不能在 $x$ 的子树中（若在子树内，不可能使重心移动至 $x$）。

所以可以 $\texttt{DFS}$，树状数组维护每个大小的 $siz$ 的出现次数，查询区间和。对于在 $x$ 内部的边产生的贡献，可以再开一个树状数组，跟着 $\texttt{DFS}$ 的过程加入值，然后记录遍历 $x$ 的子树前后的值，作差即可。

再考虑 $rt$ 的贡献，令 $u,v$ 为 $siz$ 前二大的子树。如果删去的边在 $u$ 的子树，则 $2 \times siz_v \le n - S$，否则 $2 \times siz_u \le n - S$。这个也可以在 $\texttt{DFS}$ 的过程中维护。

[NOIP 2018]保卫王国

给定一棵树，点带权，每次强制两个点选或不选，询问独立，求树的最小权覆盖集。
$ n \le 10^5,m \le 10^5$

首先考虑不带修改的做法，定义 $dp[x][0/1]$ 为 $x$ 这个点选或不选，$x$ 及其子树的最小权值。有：

$$dp[x][0] = \sum_{y \in son(x)} dp[y][0]$$

$$dp[x][1] = w[x] + \sum_{y \in son(x)} \min(dp[y][0],dp[y][1])$$

很显然

现在考虑如何进行修改。

发现如果修改点 $\texttt{a,b}$，那么除了 $\texttt{LCA(a,b)}$ 及其祖先之外，每个点最多只有一个后代被修改，因此修改的 $\texttt{dp}$ 值形如两条链。

考虑把转移写成矩阵的形式，设 $f[x][0/1]$ 为 $x$ 的父亲的 $\texttt{dp}$ 值减去 $x$ 的贡献后的值。有：

$$f[x][0] = dp[fa[x]][0] - dp[x][1]$$

$$f[x][1] = dp[fa[x]][1] - \min(dp[x][0],dp[x][1])$$

那么从一个点 $x$ 的 $\texttt{dp}$ 转移到其父亲 $fa[x]$，有：

$$dp[fa[x]][0] = f[x][0] + dp[x][1]$$

$$dp[fa[x]][1] = f[x][1] + \min(dp[x][0],dp[x][1])$$

实际上就是把上面两个方程移了下项。

如果把乘法定义为:

$$c_{i,j} = \min\{a_{i,k}+b_{k,j}\}$$

那么方程写成矩阵乘法的形式就是：

$$\begin{pmatrix} dp[fa[x]][0] & dp[fa[x]][1] \end{pmatrix} = \begin{pmatrix} dp[x][0] & dp[x][1] \end{pmatrix} \times \begin{pmatrix} +\infty & f[x][1] \\ f[x][0] & f[x][1] \end{pmatrix}$$

这个东西满足结合律，所以我们可以直接定义一个倍增矩阵数组：$g[x][i]$ 为 $x$ 的 $\texttt{dp}$ 值向上跳 $2^i$ 步中途乘的矩阵的积。这样就可以在 $\log$ 的时间内通过一个点的 $\texttt{dp}$ 值得到整棵树的了。

现在考虑修改，也就是把修改的点上不满足条件的（强制放或不放）那一项 $\texttt{dp}$ 改成 $+\infty$，然后再倍增向上跳即可。需要特殊注意两个点合并时的情况。

具体来说，若两点是祖先关系，那么可以跳到同一点后将两者中祖先的限制加入后代的 $\texttt{dp}$ 矩阵中，然后继续向上跳到根节点。否则，在 $\texttt{LCA}$ 处会出现一个节点的两个儿子同时被修改，特殊判断一下，修改转移矩阵即可，然后再继续跳到根节点。

复杂度 $O(n\log n+m\log n)$

[CSP-S 2019]树上的数

咕咕咕

[CSP-S 2020]贪吃蛇

考虑如果一条蛇选择结束，需要满足什么条件。

如果他吃掉最后一名之后，没有变成最后一名，那么他一定选择吃。称这样是必吃状态。

由于整个序列是递增的，如果他吃了最后一名而没有掉到最后一名，会使得序列的 $\min$ 增大，$\max$ 减小。那么新的第一名如果选择吃，那一定会落到原先第一名更后面。

那就让新的第一名去选择是否结束，反正我吃了不会比他先死。

如果他吃掉最后一名之后，变成了最后一名，那么找到距离他最近的必吃状态，我吃不吃只和与这个必吃状态的 距离 的 奇偶性 相关。

设我在 $p$，最近的必吃状态位置是 $s$。

首先显然的是 $s$ 处必定会吃，那考虑 $s$ 到 $p$ 之间的蛇，他们一定不是必吃状态，那一定有：这些蛇选择吃之后的新状态的体力值单调。

也就是说，如果 $s$ 吃，他一定吃的是 $s+1$。$s+1$ 知道自己会被吃，那么他就选择不吃最小的；$s+1$ 不吃，就会选择结束，那么 $s+2$ 就知道自己就算变成最后，也不会死，那么他一定选择吃......

也就是，如果 $p-s$ 是奇数，他就会结束游戏，否则一定会吃掉最小的，而接下来新的第一名就一定会直接结束游戏。

然后拿队列模拟一下，和 $\text{NOIP2016}$ 蚯蚓一样维护一个双端队列，每次从原队列和新队列取 $\max$ 和 $\min$ 更新即可。

只要遇上一个非必吃状态，就 $\mathcal{O(n)}$ 模拟找到下一个必吃状态，返回答案即可。

时间复杂度 $\mathcal{O}(n)$。