联赛真题LIST

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

不过应该会咕得比较厉害

[CSP-S 2019]树的重心

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

$n\le 3\times {10}^5$

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

$$maxso{n}_x\times 2\le n-S$$

$$(n-S-si{z}_x)\times 2\le n-S$$

化简得：

$$n-si{z}_x\times 2\le S\le n-maxso{n}_x\times 2$$

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

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

再考虑 $rt$ 的贡献，令 $u,v$ 为 $siz$ 前二大的子树。如果删去的边在 $u$ 的子树，则 $2\times si{z}_v\le n-S$，否则 $2\times si{z}_u\le n-S$。这个也可以在 $\mathtt{\text{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])$$

很显然

现在考虑如何进行修改。

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

考虑把转移写成矩阵的形式，设 $f[x][0/1]$ 为 $x$ 的父亲的 $\mathtt{\text{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$ 的 $\mathtt{\text{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}\}$$

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

$$\left(\begin{array}{cc}dp[fa[x]][0]& dp[fa[x]][1]\end{array}\right)=\left(\begin{array}{cc}dp[x][0]& dp[x][1]\end{array}\right)\times \left(\begin{array}{cc}+\mathrm{\infty }& f[x][1]\\ f[x][0]& f[x][1]\end{array}\right)$$

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

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

具体来说，若两点是祖先关系，那么可以跳到同一点后将两者中祖先的限制加入后代的 $\mathtt{\text{dp}}$ 矩阵中，然后继续向上跳到根节点。否则，在 $\mathtt{\text{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}\mathcal{(}\mathcal{n}\mathcal{)}$ 模拟找到下一个必吃状态，返回答案即可。

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