2024年12月一些算法比赛（一）

[[ slider_text ]]

[[ item.c ]]

2024年12月一些算法比赛（一）

发布时间 2024-12-16 作者：zhangminchen 来源：算法小站

莫队 树的重心

## 树的重心
### 树的重心定义，性质
对于每个节点$$u$$，计算它所有子树中，最大的子树的节点数，使得这个最大值最小
那么这个节点$$u$$就是树的重心

性质
> 点$$u$$是重心，以$$u$$为根时，所有子树大小 $$\leqslant \dfrac{n}{2}$$

证明，如果存在一个重心，使得某个子树大小$$> n/2$$，那么沿着这个子树方向走一条边，一定有一个更优的重心
另一方面，以$$u$$为根时，所有子树大小$$\leqslant n/2$$，如果选择$$u$$的邻居$$v$$
那么以$$v$$为根时，子树大小$$\geqslant n - n/2 = n/2$$，$$v$$必然不是重心

> 重心至少有一个，最多有两个
如果有双重心，那么它们之间至少有一条边相连，并且树中一定有**偶数**个节点
同时存在一种方式，分割成两棵树，使得这两个重心分别为两棵树的重心
如果有双重心，那么一定是$$(u, pa_u)$$（dfs 的时候它们互为父子）

证明，一个重心和两个重心的情况很好证明，如果有$$3$$个重心呢？那么每 2 个重心之间一定有边相连
这就形成了大小为 3 的环

如果有两个重心，就以为着有两个大小都是$$\dfrac{n}{2}$$的子树，**可以根据这个来判断是不是双重心**

> 重心的判断很简单，`dfs`一遍求`sz`，一开始所有的`center(u) = 1`，`dfs(u)`的时候，看子树大小
如果`sz(v) > n / 2`，不是重心，遍历所有子树之后，如果`n - sz(u) > n / 2`，也不是重心

代码实现见后面

> 点$$u$$为重心，树中所有点到某个点的距离之和中，到重心$$u$$的距离之和是最小的
如果有双重心，那么到它们俩的距离之和一样

因为算距离之和，所以对于$$v$$，它的子树等价转换成**子树节点深度都是 1**
这样所有点到$$v$$的距离之和都是$$\text{size}(v)$$

如果某个点不是重心，那么存在一棵子树，使得$$\text{size} > \dfrac{n}{2}$$，这样这棵子树的贡献一定$$> n / 2$$
反过来看重心，重心所有子树的贡献都$$\leqslant \dfrac{n}{2}$$，所以重心能够使得距离之和最小

> 把两棵树通过一条边相连得到一棵新的树，新的树的重心，在连接原来两棵树的重心的路径上
并且这个新重心，会落在原重心较大的那棵树的一侧

动态地看，把较小的那棵树，一个个作为叶子结点，和较大的那棵树合并
不难发现，小重心，会逐渐向大重心移动

> 在一棵树上，添加或者删除一个叶子，重心最多只会移动一条边的距离

### Codeforces Round 670 (Div. 2) C
**[C. Link Cut Centroids](https://codeforces.com/contest/1406/problem/C)**
给定一棵树，我们切掉一条边，再加一条边，使得新的树仍然是一棵树，并且仅有一个重心
输出切掉的边，和加上的边

**算法分析**
1）如果原来就只有一个重心，什么事都不用做
2）否则的话，双重心，不妨设为$$c_1, c_2$$
因为双重心，那么以它们为根，两棵子树的大小都是$$\dfrac{n}{2}$$，并且$$n$$为偶数
此时断开$$(c_1, c_2)$$，如果选择将`c2子树`的一个叶子结点断开，和`c1` 相连
那么两棵子树的大小分别变成了$$\\{n/2+1, n/2-1\\}$$，小重心会向大重心移动
因为我们只添加一个叶子结点，所以重心最多只移动一条边，$$c_1$$就会变成新的重心

```bash
void solve() {
    vector<int> sz(n+1, 0), sgn(n+1, 1);
    auto dfs = [&](auto &self, int u, int pa) -> void {
        sz[u] = 1;
        for (auto v : g[u]) {
            if (v == pa) continue;
            self(self, v, u);
            sz[u] += sz[v];

if (sz[v] > n / 2) sgn[u] = 0;
        }
        if (n - sz[u] > n / 2) sgn[u] = 0;
    };
    dfs(dfs, 1, 0);

vector<int> center;
    for (int i = 1; i <= n; i++) if (sgn[i]) center.push_back(i);
}
```

### Codeforces Round 359 (Div. 1)
**[B. Kay and Snowflake](https://codeforces.com/contest/685/problem/B)**
**问题描述**
给定 1 为根的有根树，$$q$$次询问，每次回答以$$u$$为根的子树中，重心是哪个？
（注意，这里的回答是独立的，子树要求和其他部分断开）

**算法分析**
> 一个结论，$$u$$子树的重心，肯定在$$u$$的重儿子里

可以先求出重儿子$$hs_u$$的重心，看看$$hs_u \to u$$，重心是怎么变化的
第一遍 dfs 进行树链剖分，求出重儿子

接着考虑重心的变化
1）如果$$u$$的重儿子的$$sz \leqslant sz_u / 2$$，那么$$u$$本身就是重心
2）考虑$$u$$的重儿子$$v$$，假设说我们已经求出了$$v$$的重心，是`ctr`
首先考虑`ctr`会不会依然是重心？这是有可能的，根据重心的定义检验一下
`sz( hs(ctr) ) <= sz(u) / 2 and ( sz(u) - sz(ctr) ) <= sz(u) / 2`满足的话，仍然是重心

否则重心会变化
![](/media/content_img/CF359B.png)
它沿着`parent`往上爬，在爬的过程中，继续暴力判断，直到满足条件，这就是`u`的新重心
因为最多爬一次，所以复杂度还是$$O(n)$$的

## Codeforces Round 990 (Div. 2)
**[E. Adventurers](https://codeforces.com/contest/2047/problem/E)**
找一个点$$(x_0, y_0)$$，把平面分成 4 部分，要求
第一部分点满足$$x_i \geqslant x_0, y_i \geqslant y_0$$
第二部分满足$$x_i < x_0, y_i \geqslant y_0$$
第三部分满足$$x_i \geqslant x_0, y_i < y_0$$
第四部分满足$$x_i < x_0, y_i < y_0$$

现在要使得四个部分的点数，最小值最大

### 算法分析
典型的**二维偏序问题**
可以用**两棵线段树**，`tr1`维护左半平面，`tr2`维护右半平面，一开始`tr1`空的，`tr2`拥有全部的点
然后扫描线扫过的时候，`tr1`把扫描线上的点加上，`tr2`把相应的点减去

不难想到，主算法是二分，二分`mid`，判断四部分点的个数是不是都$$\geqslant mid$$
并且尝试最大化这个`mid`，`check`就判断四部分点数是不是$$\geqslant mid$$即可

这样对于$$y_i < y_0$$以及$$y_i \geqslant y_0$$的情况，都可以确定下来了，分别对应扫描线的左右两个半平面

那么怎么确定$$x_0$$
只需要对`tr1`，在线段树上二分，找到第一个**前缀和`sum >= mid`**的位置$$p_1$$（前缀和就对应左半平面点的个数）
对`tr2`也同理找到这样的位置$$p_2$$，那么$$x = \max(p_1, p_2)$$
此时四个部分都可以确定下来了，在两棵线段树上，分别把这四部分计算出来，看看是不是都$$\geqslant mid$$即可

> 编程难点

实现起来稍微有点困难的就是线段树二分，要找到前缀和第一个$$\geqslant mid$$的位置
需要注意的是，递归时候用`info`来累计信息，往右子树走的时候，**`info`要累加**上左子树的对应的整段区间和

```bash
int K = 0;
bool sgn(int info) {
    return info < K;
}

K = mid

// 找到第一个满足条件的位置 p
// 使得 sum(1...p-1) < K   --->  true
// sum(1...p) >= K   ---> false

template<bool (*f)(S)>
int max_right(int p, int l, int r, S info) {
	if (l == r) return l;
	int mid = (l + r) >> 1;

if (f(op(info, node[p<<1])) == false) return max_right<f> (p<<1, l, mid, info);
	else return max_right<f> (p<<1|1, mid+1, r, op(info, node[p<<1]));
}
```

## AtCoder Beginner Contest 384
### E
**[E - Takahashi is Slime 2](https://atcoder.jp/contests/abc384/tasks/abc384_e)**
**问题描述**
给定一个矩阵，一开始`info = a(p, q)`，考虑当前**所有边界**，边界相邻的点`a(x, y) * X < info`
那么`(x, y)`就会被`info`吸收，问最多能吸收多少，使得`info`值最大，输出这个最大值

> 不难想到套用宽搜的框架

套用宽搜的框架，需要一个`ins(x, y)`，来标记一下`(x, y)`这个点是否进过队列
`que.push( {x, y} )`的时候，令`ins(x, y) = 1`，扩展的时候，如果`ins(nx, ny)`，那么忽略`(nx, ny)`这个点

> 可以贪心求解

不难发现，对于宽搜的每一层，我们应该吸收尽可能多的点，策略是
**从小到大吸收，直到不能吸收为止**，维护一个**小根堆**
1）如果当前不能吸收了，最小的都吸收不了，肯定无法继续了，break 掉
2）否则，吸收当前的堆顶元素，注意到每吸收一层，又会多出`4 个相邻元素`，将它们都要放入堆中
贪心目标是吸收尽可能多的元素，我们每次在堆中找最小的吸收

> 证明如下

如果有两个元素`(a, b)`，$$a < b$$，若`info > b * X`，那么不论怎么样都可以吸收`a, b`
而如果`info < b * X`呢，先吸收$$a$$可以增大`info`值，他有可能$$> b \cdot X$$，有可能吸收掉$$b$$
所以先吸收小的元素，并不会使结果变差

### F
**[F - Double Sum 2](https://atcoder.jp/contests/abc384/tasks/abc384_f)**
计算$$\displaystyle \sum\_{i = 1}^{n} \sum\_{j = i}^{n} f(A\_i + A\_j)$$

其中$$f(x)$$定义如下，$$2^{k} \mid x$$，但是$$2^{k+1} \nmid x$$，$$x$$恰好能被$$2^k$$整除
那么$$f(x) = x / 2^k$$

**算法分析**
考虑对$$2$$的幂指分类，假设第$$k$$类，表示恰好能够被$$2^k$$整除的$$(A_i,A_j)$$，有什么性质呢？

假设我们考虑$$x = A_i$$，维护前缀已经出现过的数$$A_j$$，不难发现
对于$$\bmod 2^k$$，有
```bash
x + A(j1)
x + A(j2)
x + A(j3)
.....
x + A(jm)
```
都是符合条件的，它们的和是$$cnt\cdot x + \sum A(j_i)$$，能不能维护起来呢？

> 那要看这些数都有什么特点？

这些数的共同点就是$$(x + A_j) \bmod 2^k \equiv 0$$
换句话说，满足条件的前缀，这些数都在集合$$\\{-x \bmod 2^k\\}$$中，那么就很容易维护了

直接用一个`st[ -x % 2^k ] = { cnt, sum }`，遍历到$$i$$的时候，$$x = A_i$$
考虑`auto &[cnt, sum] = st[ -x % 2^k ], cnt += 1, sum += x`即可

计算答案的时候，$$x \equiv -A_j (\bmod 2^k)$$，直接在`st[ x % 2^k ]`中查询`(c2, s2)`
对第$$k$$类答案的贡献就是$$c2 \cdot x + s2$$

> 恰好被$$2^k$$整除，这类的技术问题，对每个$$k$$单独考虑之后，$$cnt(k) - cnt(k+1)$$
这是这种问题常用的思路，包括`gcd`也有类似的结论，`gcd的个数 - gcd 倍数的个数`

计算最终答案的时候
所有恰能被$$2^k$$整除的，$$x + A_j$$的和，可以用$$ans = res(k) - res(k+1)$$来求解
最后的答案就是$$ans / 2^k$$

### G
**[Abs Sum](https://atcoder.jp/contests/abc384/tasks/abc384_g)**
给你两个序列$$A, B$$，$$K$$个询问，每次询问给出$$X_k, Y_k$$，求解
```math
\displaystyle
\sum_{i = 1}^{X_k} \sum_{j = 1}^{Y_k} |A_i - B_j|
```

**算法分析**

> 考虑对于特定的$$x$$，其中$$x \in [1, X_k]$$，我们怎么做？实际上是求关于$$f(x)$$的前缀和

我们有
```math
\displaystyle
f(x) = \sum_{j=1}^{Y_k} |A_x - B_j| = \sum_{j = 1}^{Y_k} (A_x + B_j - 2\min(A_x, B_j)) \\
= Y_k \cdot A_x  + \left( \sum_{j=1}^{Y_k}B_j \right) - 2\cdot\left( (Y_k - B[1\cdots Y_k]\text{ 中有多少个} < A_x \text{ 的数})\cdot A_x + B[1\cdots Y_k] \text{ 中 } < A_x \text{ 的数的和} \right)
```

注意到$$f(x)$$中的每一项，都可以在至少$$O(\log n)$$的复杂度内算出来，用**树状数组**
那么对于$$x \in [1, X_k]$$，可以考虑暴力前缀和

> 那这个问题多组询问，对特定的询问，暴力的复杂度是$$O(\log n)$$，同时又是关于一个前缀和问题
关于$$x+1$$的答案可以从$$x$$递推而来，可以考虑**离线莫队**

对称地，我们有
```math
\displaystyle
g(y) =  X_k \cdot B_y  + \left( \sum_{i=1}^{X_k}A_i \right) - 2\cdot\left( (X_k - A[1\cdots X_k]\text{ 中有多少个} < B_y \text{ 的数})\cdot B_y + A[1\cdots X_k] \text{ 中 } < B_y \text{ 的数的和} \right)
```

> 这样，算法就比较容易设计了

考虑暴力$$(0, 0) \to (0, Y_1) \to (X_1, Y_1)$$，然后再重复这个过程，计算$$\Delta$$值的变化
考虑$$(X_1, Y_1) \to (X_1, Y_2) \to (X_2, Y_2)$$，以此类推

莫队算法执行过程如下
1）一开始的时候，$$x = X_k = 0, y = Y_k = 0$$，先令$$X \to X_1$$，此时`关于 B 的树状数组中`未添加任何数
此时$$f(x)$$计算的结果是$$0$$
但是，这个时候在$$x \to X_1$$的过程中，要把`A 的值添加到关于 A 的权值树状数组中`
这样$$x$$跑到$$X_1$$的时候，就维护好了$$[1\cdots X_k]$$的所有数（区间范围之外的数，还未添加）
这时候$$g(y)$$就可以正确求解

2）考虑$$y \to Y_1$$，这个时候`树状数组 A 的值暂时固定`，每个$$g(y)$$都可以暴力地，正确求解
一边求解，一边累加答案，等到$$y = Y_1$$的时候，我们就计算好了$$(0, 0) \to (0, Y_1)$$的值了
与此同时，跑的时候要把`B`相关的值加入树状数组中，维护起来

3）每个$$g(y)$$被暴力累加起来的时候，因为$$\displaystyle g(y) = \sum\_{i = 1}^{X\_1} |A_i - B_y|$$

从而$$\displaystyle \sum\_{y = 1}^{Y\_1} g(y) = \sum\_{i=1}^{X\_1}\sum\_{j = 1}^{Y\_1} |A_i - B_j|$$，$$(X_1, Y_1)$$被正确求解

4）注意到此时$$y = Y_1$$，并且$$B[1\cdots Y_1]$$中的信息已经维护好
只要令$$x$$跑$$X_1 \to X_2$$，考虑变化了多少，就可以基于$$(X_1, Y_1) \to (X_2, Y_1)$$

然后此时$$X_2$$又暂时固定，$$(X_2, Y_1) \to (X_2, Y_2)$$

以此类推，重复以上过程即可，相当于$$(x, y)$$，先让$$x$$跑到$$X_1$$，然后固定下来
接着让$$y$$跑到$$Y_1$$，固定下来，这样计算出$$(X_1, Y_1)$$
接着$$x$$只需要跑到$$(X_1 \to X_2)$$这一段，$$Y_1$$不变，然后继续

> $$(x, y)$$，相当于一个坐标先跑到目标位置，然后暂时固定，等另一个坐标到目标位置，统计答案
然后接着只需要看两个坐标相对跑了多远？暂时固定一个，跑另一个

这个题目的坑点是，$$x, y$$坐标是相互依赖的，你要在$$B$$中查询关于$$< A_x$$的数
所以$$A, B$$要放一块离散化，不能单独离散化

上一篇：最大流和匹配下一篇：2024年12月一些算法比赛（二）

看完文章有啥想法