树上问题，DSU on Tree，启发式合并

[[ slider_text ]]

[[ item.c ]]

树上问题，DSU on Tree，启发式合并

发布时间 2023-06-13 作者：zhangminchen 来源：算法小站

并查集 启发式合并 DSU on Tree

## 启发式合并
### 问题描述
记$$|S|$$为集合$$S$$中元素的个数，对于两个集合$$|S_x|, |S_y|$$，尝试将**小集合并入大集合中**
令$$|S_x| \leqslant |S_y|$$，那么
```bash
for z in Sx:
    把 z 放入 Sy 中

清空 Sx
```
这样做的时间复杂度是$$O(n \log n)$$ 的

**证明**
考虑每个元素的贡献，假设$$|S_x| \leqslant |S_y|$$，那么考虑$$|S_x |\to |S_x \cup S_y|$$
合并之后的集合 $$|S2_x| \geqslant 2|S_x|$$，最后集合的大小是$$O(n)$$
由此 $$|Sk_x| = O(n) \geqslant 2^{k} |S_x|$$，从而 $$k = O(\log n)$$
也就是说，只需要合并$$O(\log n)$$次，所以代价是 $$O(n \log n)$$

**[HNOI 梦幻布丁](https://ac.nowcoder.com/acm/problem/20076)**
**问题描述**
$$n$$ 个布丁，$$m$$ 次操作，$$a_1,\cdots, a_n$$ 表示每个布丁的颜色
`1 x y` 将颜色 `x` 的布丁变成颜色 `y`
`2` 询问一共有多少段颜色

**算法分析**
> 询问多少段颜色，是比较简单的

```bash
for i = 2 to n:
     只要 a[i] != a[i-1]，ans += 1
```

>  现在看修改颜色的时候，如何维护答案

比如将 `a[i]` 的颜色改为 `c`，段数会怎么变化呢？可以 $$O(1)$$ 来维护
如果`a[i] == a[i-1]`，那么 `i` 这个位置**对答案的贡献**是`1`
否则，对答案的贡献是`0`（`a[i]`和`a[i+1]`也是同理）

```bash
modify 函数：
ans -= ( a[i] != a[i-1] ) + ( a[i] != a[i+1] )
a[i] = c
ans += ( a[i] != a[i-1] ) + ( a[i] != a[i+1] )
```

>  具体怎么去修改颜色呢？

注意到，我们只需要求布丁有几段，一个位置$$i$$对答案的贡献，只和
`a[i] =? a[i-1],  a[i] =? a[i+1]`有关，和`a[i]`的值具体是多少没有关系
将颜色`x`的布丁全部变成颜色`y`， **等价于**把颜色`y`的布丁变成`x`

根据启发式合并，只需要把颜色`x`的布丁**所有位置**用 `pos[x]` 存起来
保证`pos[x].size() <= pos[y].size()`，把 `pos[x]`中的元素合并到`pos[y]`中去

**特别注意**
启发式合并中可能会有`swap(pos[x], pos[y])`的操作，来保证`pos[x]`集合大小一定小于`pos[y]`

> 比如 `{1, 4, 5, 7}`的颜色是`x`，`{2, 3]`的颜色是`y`，但是交换集合之后
  `{1, 4, 5, 7}` 的颜色变成了`y`了，在`a[...]`数组这些位置的颜色也要对应改成`y`
  执行上述 modify 函数，改的时候同时维护答案
  
**另外**，为了处理边界，在`a[0], a[n+1]`加入两个哨兵，值为`0`
这样答案就是`ans - 1`，避免了复杂的边界讨论

###  启发式合并解决路径最小值
**问题描述**
给定$$n$$个点的树，和$$q$$个询问，每次询问路径$$u, v$$上的最小值

**算法分析**
考虑**将询问离线**，根据边权，**从大到小**加入边，当前边假设是$$(u, v)$$
维护**两个点集**，$$u$$所在的点集是$$SU$$，$$v$$所在的点集为$$SV$$
（假设$$(u, v)$$的权值为$$w$$）

如果加入$$(u, v)$$**恰好**使得$$SU, SV$$**连通**，而此时恰好又有询问$$(qu, qv)$$
$$qu \in SU, qv \in SV$$，那么$$w$$就是询问$$(qu, qv)$$的答案

**证明**
对于两个点$$(u, v)$$，考虑路径$$u \to v$$，路径上删除任意一条边，都会使得$$(SU, SV)$$不连通
反之，**路径上**边权最小的边，就是满足
加入这条边后，$$(SU, SV)$$能够**恰好连通**，这样的边取权值最小的那个，就是答案

**算法实现**
*  用并查集维护两个点集
*  对两个点集，相应地维护询问集合，即将询问`(qu, qv)`挂载到对应的点`(u, v)`上
*  启发式合并`su, sv`，同时维护答案

具体来说，按边权**从大到小**加入边，对于边$$(u, v)$$找到集合$$SU, SV$$
启发式合并，尝试将$$SU \to SV$$，需要保证$$|SU| \leqslant |SV|$$，合并的同时维护答案

暴力检查$$|SU|$$中的每一个点，以及这个点上**挂载**的所有询问

> 如果用并查集的话，$$|SU|$$集合中的所有询问，就是`u = findpa(u)`
   `que[u]`中挂载的所有询问

即检查`que[u]`中的**所有询问**

* 
	如果某个在`que[u]`中的询问`id`，这个询问已经**被解决**了，什么都不做
	> 实际上可以从`que[u]`中删除，但`set`的删除带一个`log`，所以可以标记询问已被解决
	> 这样可以提高程序运行时间
	
*	如果该询问的另一个端点在$$|SV|$$中，更新`ans[询问id] = w(u, v)`

*  如果不在$$|SV|$$ 中，就把这个询问加入到$$|SV|$$中

做完之后，把$$SU$$中的点全部并入$$SV$$中，这里需要注意的是
我们需要知道**点到底在哪个集合中**，要用`belong[u]`去记一下

## 启发式分治
**问题描述**
给定长为$$n$$的序列$$a_1, \cdots, a_n$$，定义序列$$a$$是一个好序列，当且仅当
它的**每一个子区间**$$[l, r]$$满足，至少存在一个元素$$x$$，它**只出现一次**

**算法分析**
> 什么情况下，一个序列**一定不是**好序列？

对于一整段$$a[1\cdots n]$$，只需要找到一个$$x$$，满足$$x$$在$$[1, n]$$中只出现一次
那么这个序列就**可能**是好序列，否则就**一定不是**好序列

> 假设我们找到了满足条件的$$x$$了，然后呢？

$$x$$ 在一整段中都只出现了一次，那么对于**所有包含**$$x$$的子区间中
$$x$$ 也只出现一次，所以只需要检查不包含$$x$$的区间就可以了
`[1, pos[x]-1], [pos[x]+1, n]`，这样就可以考虑分治

> 考虑分治策略

对于$$[l, r]$$，我们找到整段区间中仅出现一次的元素$$x$$和它的位置
这个很容易找，只需要预处理，得到上一次出现和下一次出现，
满足`pre(x) < l`并且`nxt(x) > r`即可

问题是分治的时间复杂度，分治可能会存在**划分不均匀问题**
如果$$x$$每一次都在靠两端的位置，那么每一次找$$x$$的代价可能是$$O(n)$$的
总的复杂度退化到$$O(n^2)$$
如果$$x$$在中间，那么分治策略复杂度是$$O(n\log n)$$，只需要考虑两端位置

解决方法是，**启发式分治**，用两个指针，每次分别从前往后，和从后往前找
尝试找到这样的`x`
```bash
for (int pl = l, pr = r; pl <= pr; pl++, pr--) {
	if (pre[pl] < l && nxt[pl] > r) 
		// 继续分治
	if (pre[pr] < l && nxt[pr] > r)
		//
}
```
> 启发式分治复杂度

$$T(n) = T(x) + T(n-x) + O(\min (x, n-x))$$

也就是每一次合并的代价，只和**较小的那个集合**有关，复杂度$$O(n \log n)$$

## DSU on Tree
**算法概述**
我们需要维护一类有关**子树信息**的问题，比如树上点都有一种颜色，问任意一个点
它的子树中有多少种不同的颜色

一种算法思想是，考虑**子树合并**，合并的同时维护信息，并且转移到父亲，以此类推
子树合并可以考虑**启发式合并**
> 简单来说，先把一个点的子树集合合并，然后再把集合和这个点本身的集合合并

**算法实现**
对于每个点，找到**集合大小最大**的儿子（也就是点个数最多），称为**重儿子**
其他的儿子称为**轻儿子**

假设当前的点是$$u$$，先把$$u$$的**重儿子**集合找出来，记为$$|HS|$$
将$$u$$并到$$|HS|$$中，再把轻儿子集合并到$$|HS|$$中

> 具体来说，$$S(u)$$ 表示$$u$$这个点的集合，可以直接从重儿子继承过来
  轻儿子依次合并到$$S(u)$$中
  其实我们不需要维护轻儿子的集合，只需要`for`轻儿子子树中的所有节点
  
**代码实现**

先`dfs`整棵树，求出`dfs`序，并且维护树的结构

* `id[tot] = u`，记录`dfs`序下标`tot`对应原树的节点`u`
* `sz[u]` 维护`u`及其子树的大小
* `hs[u] = v`，记录`u`的重儿子是`v`

接着做`DSU on Tree`
`dfs(int u, int fa, bool keep)`

* `keep` 参数的意义
  如果一个点是重儿子，那么它的信息要**继承到父亲**上
  如果是轻儿子，算出信息回溯的时候，不需要轻儿子携带的信息
  `keep` 表示计算完成，回溯的时候，需不需要保留节点的信息
  
* 先`dfs`轻儿子，计算出轻儿子集合，和它携带的信息，`dfs(轻儿子v, u, false)`
  再`dfs`重儿子，计算出重儿子集合和携带信息，`dfs(hs[u], u, true)`
  
* 将`u`的所有轻儿子及其子树节点，加入到重儿子集合中
  可以考虑`dfs`序列，如果`v`是**轻儿子**，它的子树就是`dfs`序中`l[v], r[v]`
  ```bash
  for x in [ l[v], r[v] ]:
      add( id[x] )
  ```
  然后将`u`本身也加入到重儿子集合中，`add(u)`
  
*  最后，如果`keep == false`，那么清空`u`及其子树集合中所有信息
   `for x in [ l[u], r[u] ]`，执行`del(id[x])`
   
### 代码实现及应用
```bash
int n;
vector<vector<int> > G(n+1);

vector<int> l(n+1, 0), r(n+1, 0), id(n+1, 0),
    sz(n+1, 0), hs(n+1, -1);

int tot = 0;

function<void(int, int)> dfs_init = [](int u, int fa) -> void {
    l[u] = ++tot, id[tot] = u;
    sz[u] = 1;
    hs[u] = -1;

for (auto v : G[u]) {
        if (v == fa) continue;
        dfs_init(v, u);

sz[u] += sz[v];
        if (hs[u] == -1 || sz[v] > sz[ hs[u] ]) {
            hs[u] = v;
        }
    }

r[u] = tot;
};

auto add = [](int u) -> void {
    //
};

auto del = [](int u) -> void {
    //
};

function<void(int, int, int)> dfs 
= [](int u, int fa, bool keep) -> void {
    // dfs light son
    for (auto v : G[u]) {
        if (v != fa && v != hs[u]) {
            dfs(v, u, false);
        }
    }

// dfs heavy son
    if (hs[u] != -1) {
        dfs(hs[u], u, true);
    }

// combine light son -> heavy son
    for (auto v : G[u]) {
        if (v != fa && v != hs[u]) {
            for (int x = l[v]; x <= r[v]; x++) add(id[x]);
        }
    }
    // add u
    add(u);

if (!keep) {
        // clear info in node u
        for (int x = l[u]; x <= r[u]; x++) del(id[x]);
    }
};

void solve() {
    dfs_init(1, 0);
    dfs(1, 0, false);
}
```

**[CF600E.  Lomsat gelral](https://codeforces.com/problemset/problem/600/E)**
**问题描述**
给定$$n$$个节点的有根树，$$1$$号节点为根
每个节点都有一个颜色，第$$i$$号节点颜色编号为$$c_i$$
如果一种颜色在以$$x$$为根的子树中**出现次数最多**，那么称它在$$x$$为根的子树中占主导地位
显然，同一棵子树中，可能有多种颜色占主导地位

对每一个$$i \in [1, n]$$，输出以$$i$$为根的子树中，占主导地位的颜色的编号和

**算法分析**
只需要稍微更改一下`DSU on Tree`的主过程，对于每个点$$x$$，需要知道以下信息并维护
*  `c[x]` 表示节点`x`的颜色
*  `cnt[ col ]` 表示颜色`col` 出现了多少次
*  `maxcnt` 表示当前**出现次数最多的**是什么颜色
*  `sum` 维护 `x` 及其子树，出现次数最多的颜色，它们的**编号和**

这样可以写出如下代码
```bash
auto add = [&](int x) -> void {
	int col = c[x];
	cnt[col]++;
	
	if (cnt[ col ] > maxcnt) maxcnt = cnt[ col ], sum = 0;
	if (cnt[ col ] == maxcnt) sum += col;
};

// 在 add(u) 之后，令
ans[u] = sum
```

**另外需注意**，清空的时候，同样上述信息要维护好
```bash
auto del = [&](int x) -> void {
	int col = c[x];
	cnt[col]--;
};
// 同 DSU on Tree 的模版
if (!keep) {
	del(id[x]);
	maxcnt = 0, sum = 0;
}
```

### IOI2011 Race
**[IOI2011 Race](https://www.luogu.com.cn/problem/P4149)**
**问题描述**
给一棵树，每条边有边权，求一条简单路径，权值和等于$$K$$，且边的数量最小

**算法分析**
> 先考虑找到一条路径，使得它的权值和为 $$K$$，这应该怎么做呢？

注意到 `dis(u, v) = dep(u) + dep(v) - 2*dep( lca(u, v) )`，可以考虑**枚举LCA**

假设当前枚举的`LCA`是`x`，那么我们要在`x`的子树中找到两个点`u, v`，使得
$$\text{wdep}(u) + \text{wdep}(v) - 2\cdot \text{wdep}(x) = K$$，两个子树问题，可以考虑`DSU on Tree`
**其中**，$$\textbf{wdep}(x)$$ 表示$$x$$到**根节点**路径上的**权值和**

对于每个点$$x$$，维护重儿子集合$$|SU|$$，并且`for`它的轻儿子$$v$$，对于每个$$v$$，先做一次查询
尝试在$$|SU|$$中找到一个点$$u$$，使得它到根节点路径的权值和为
`K + 2*wdep(x) - wdep(v)`，如果能找得到这样的`u`，怎么更新答案呢？

> 考虑更新答案，答案要求边数量最小

考虑用哈希表维护，`mp[ wdep ] = dep`，简单来说，建立映射
`到根节点的权值和 --> min( 到根节点的最小边数 )`，对于一个点`u`
`mp[ wdep(u) ] = min( ...,  dep(u) )`，其中`dep(u)`就表示`u`到根节点的边数

哈希表维护**最小边数**
`mp[ wdep ] = 到根节点的权值和是wdep时，此时到根节点的最小边数`

> 这样，去维护**重儿子**的哈希表，就可以更新答案了

对于`d = K + 2*wdep(x) - wdep(v)`，如果能在哈希表中找到这样的`d`
那么它到根节点的最小边数是`mp[d]`，此时令
`ans = min(ans,  mp[d] + dep[v] - 2*dep[x] )`，这样就更新完成了

>  接着尝试将`v`加入到哈希表中

实际上只需要更新`mp[ wdep(v) ] = min( mp[wdep(v)],  dep[v] )`

**值的注意的是**，在每一次`add`的时候，需要做`查询，更新`
在接下来`del`的时候，清空操作，实际上只需要把`mp`哈希表清空即可

看完文章有啥想法

zhangminchen

赞

2023-06-23 18:33:30
点赞（0）回复（5）

zhangminchen @ zhangminchen

不错不错～

2023年6月24日 02:59
点赞（0）回复（0）

zhangminchen @ zhangminchen

可以啊～

2023年6月24日 02:59
点赞（0）回复（0）

fogsail @ zhangminchen

我也来赞一个～

2023年6月24日 03:00
点赞（0）回复（0）

fogsail @ fogsail

自己赞自己

2023年6月24日 03:00
点赞（0）回复（0）

zhangminchen @ fogsail

嗯嗯嗯～

2023年6月24日 03:01
点赞（0）回复（0）
fogsail

支持一个

2023-06-23 18:33:12
点赞（0）回复（3）

zhangminchen @ fogsail

不错不错

2023年6月24日 02:53
点赞（0）回复（0）

zhangminchen @ zhangminchen

赞一个

2023年6月24日 02:55
点赞（0）回复（0）

zhangminchen @ fogsail

先赞再说～

2023年6月24日 02:59
点赞（0）回复（0）

算法小站

树上问题，DSU on Tree，启发式合并

zhangminchen

zhangminchen @ zhangminchen

zhangminchen @ zhangminchen

fogsail @ zhangminchen

fogsail @ fogsail

zhangminchen @ fogsail

fogsail

zhangminchen @ fogsail

zhangminchen @ zhangminchen

zhangminchen @ fogsail