「笔记」一些树题

来自xcy课件的一些树题

杂题

CF1109F

Description

一个$n \times m$的网格, 每个格子有一个数, 为$1$ ~ $n \times m$的排列.

一个值域区间$[l, r](1 \le l \le r \le n \times m)$是好的, 当且仅当数值在该区间内的格子, 构成一棵树(有公共边的格子连边).

统计好区间数.

$n, m\le 2\times10^3, n\cdot m\le 2\times10^5$

Soltuion

[LCT] [数据结构] [线段树]

CF1039D

Description

有一棵$n$个点的树.

一个简单路径的集合被称为”$k$合法”当且仅当: 树的每个点至多属于其中一条路径(可以不属于), 且每条路径恰好包含$k$个点.

对于$k \in [1, n]$, 求出”$k$合法”路径集合的最多路径数.

$n \le 10^5$

Solution

[分块]

对于每个确定的$k$，显然可以直接$O(n)$从下往上贪心，尽量靠下方合并

发现当$k > \sqrt n$时答案$\le \sqrt n$，所以当$k\in (\sqrt n, n]$时，按答案分块，每块二分右端点

$O(n\sqrt n \log n)$

CF机子跑得快

「SDOI2015」寻宝游戏

[set]

本质上就是每次求树链的并

树链的并就是按dfn排序后两两点的距离

set维护一下即可

Prüfer序

HNOI2008 明明的烦恼

[prufer序列]

设$\displaystyle res = (n - 2)- \sum_{i}(d_i - 1)$，表示剩下还有多少位置可以随便填，则

$\displaystyle ans = \frac{(n - 2)!}{\prod_{i}(d_i - 1)!\times res!}\times res^{n-k}$

其中$k$表示钦定了度数的点的数量

剖分

「JSOI2016」轻重路径

Description

一棵$n$个点的有根二叉树,对它跑一边重链剖分. 如果$u$两个儿子的大小一样, 认为左儿子为重儿子。

$q$次操作, 每次删掉一个当前二叉树的叶子, 每次操作后输出重儿子的编号和.

删除一个点之后, 如果以$u$两个儿子为根的子树大小一样, 重儿子保持不变.

$n, q\le 10^5$

Solution

[树链剖分]

$size_u\le \frac12size_{rt}$是必要但不充分条件，但有了这个条件每次$size_{rt}$就会减半，十分巧妙

我感觉这个复杂度其实是$O(n\log^3n)$的。。。里面还有一层找祖先的$\log$

这道题还有个Splay维护的$O(n\log n)$的做法，不过没看懂

「十二省联考 2019」春节十二响

Description

给定一棵$n$个点, 以$1$为根的树. 每个点有权值$w_i$

你需要把所有点划分到若干个集合中, 满足每个集合内不存在两点互为祖先/后代.

每个集合的权值为其内点的权值的最大值. 一种划分的权值为划分出的所有集合的权值之和.

求划分的权值的最小值.

$n\le 2*10^5$

Solution

[启发式合并] [贪心]

对于任意一条到根的链或其子链, 其上的所有点一定分属不同的集合

贪心，每个结点的子链上面一一向比自己大的配对，即对每个点的任意两条子链，按从大到小的顺序依次合并（最大的和最大的，次大的和次大的大的和$k$的顺次合并）

用个堆维护，启发式合并

点分治

LG P2664 树上游戏

[点分治]

点分治，先不考虑路径必须不在同一子树的限制，发现每个颜色在第一次出现时，会产生其子树大小的贡献

对每个分治中心$x$, 先算出每个点到根的答案.

进入每棵子树$k$时, 把子树内的点的贡献消去, 然后对于子树内的一个点, 首先把它到$x$(不包括$x$)的颜色所产生的贡献都消去(即这些颜色第一次出现时的子树大小之和)

然后统计当前点到$x$(不包括$x$)的颜色数量$num$, 使答案加上$num \times (size_{x} - size_{k})$

---

这道题差分做法：

树分块

「SCOI2005」王室联邦

这道题的做法可以用来分块

讲做法还不如贴代码

inline void dfs (int x, int f)
{
	for (int i = Begin[x]; i; i = Next[i])
	{
		int y = To[i];
		if (y == f) continue;
		dfs (y, x);
		vec[x].insert (vec[x].end(), vec[y].begin(), vec[y].end());
		if (vec[x].size() >= B)
		{
			++cnt;
			for (int i = 0; i < vec[x].size(); ++i) 
				belong[vec[x][i]] = cnt;
			cap[cnt] = x;
			vec[x].clear();
		}
	}
	vec[x].pb (x);
}

Kruskal重构树

可以处理出一个图中只经过边权$\le k$的边所能到达的点集

「IOI2018」狼人

[kruskal重构树]

模板题

建最小, 最大生成树的重构树, 边权分别为两端点编号的最大, 最小值.

然后转化为两集合是否有交的问题了.

主席树维护.