来自xcy课件的一些树题

杂题

CF1109F

Description

一个n×mn \times m的网格, 每个格子有一个数, 为11 ~ n×mn \times m的排列.

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

统计好区间数.

n,m2×103,nm2×105n, m\le 2\times10^3, n\cdot m\le 2\times10^5

Soltuion

19-8-21-1

CF1039D

Description

有一棵nn个点的树.

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

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

n105n \le 10^5

Solution

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

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

O(nnlogn)O(n\sqrt n \log n)

CF机子跑得快

「SDOI2015」寻宝游戏

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

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

set维护一下即可

Prüfer序

[HNOI2008]明明的烦恼

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

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

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

剖分

「JSOI2016」轻重路径

Description

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

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

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

n,q105n, q\le 10^5

Solution

19-8-21-2

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

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

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

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

Description

给定一棵nn个点, 以11为根的树. 每个点有权值wiw_i

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

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

求划分的权值的最小值.

n2105n\le 2*10^5

Solution

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

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

用个堆维护,启发式合并

点分治

LG P2664 树上游戏

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

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

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

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


这道题差分做法:

19-8-27-2

树分块

19-8-24-1

「SCOI2005」王室联邦

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

讲做法还不如贴代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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重构树

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

「IOI2018」狼人

模板题

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

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

主席树维护.