Tree(LHF)
larsr
·
·
Algo. & Theory
没什么价值的题就没放进来。
树形背包
Pro 1
给一个树，每个点有个权值 b_i，点集 S 的贡献为 \prod_{i\in S} b_i。多个询问 (u,x)，求出在子树 u 中所有大小为 x 的子集贡献之和。
## Sol 1
经典树形背包，考虑分析复杂度，考虑合并两个背包，大小分别为 $x,y$：
- $x,y\le k$，相当于分成若干大小小于 $O(k)$ 的块，每个块的贡献为 $O(siz^2)$，总复杂度 $O(\frac{n}{k}k^2)=O(nk)$。
- $x\le k,y>k$，合并复杂度为 $siz_xk$，全部的 $siz_x$ 最多为 $O(n)$，复杂度 $O(nk)$。
- $x,y>k$，这种合并最多有 $n/k$ 次，复杂度 $O(nk)$。
即证明总复杂度为 $O(nk)$。
## Pro 2
给一个树，每个点有个价值 $a_i$ 和权值 $b_i$，点集 $S$ 的贡献为 $\prod_{i\in S} b_i$。多个询问 $(u,x)$，求出在子树 $u$ 中所有价值和为 $x$ 的子集贡献之和。
$x\le k$。
## Sol 2
暴力合并为 $O(\frac{nk^2}{\log k})$。
NTT 合并为 $O(nk\log k)$。
启发式合并为 $O(nk\log n)$。
考虑将三个算法合并，考虑合并两个大小为 $x,y$ 的背包：
- $x,y\le \sqrt k$，暴力合并，复杂度 $O(\frac{nk}{\log k})$。
- $x\le \sqrt k,y>\sqrt k$，启发式合并，复杂度 $O(nk)$。
- $x,y>\sqrt k$，NTT 合并，复杂度 $O(nk)$。
总复杂度 $O(nk)$。
## Pro 3
给定一棵 $n$ 个点的树和 $k$，问有多少种断边的方式使得树的每个连通块的大小都是 $k$ 或 $k + 1$。 对 $998244353$ 取模。
$1\le k < n \le 10^5$。
## Sol 3
暴力做发现一个点背包最大为 $\min(k, siz/k)$，平衡一下复杂度为 $O(n^{1.5})$。
发现如果一个子树大小小于 $k$，那么肯定是不断边的，合并也可以 $O(1)$ 懒标记。
有值的位置一定是一个小于 $O(siz/k)$ 的区间，那么可以用 Pro 1 的分析方式，复杂度为 $O(\frac{n}{k}k)=O(n)$。
## Pro 4
有一棵 $n$ 个点的有根树，第 $i$ 个点有一个重量为 $b_i$，权值为 $a_i$ 的物品，定义一组选物品的方案的权值为所选物品的权值和，**要求所选物品之间不能有边相连**，对于所有 $(x,i)(1\le x\le n,1\le i \le m)$，你需要求出 $x$ 子树内所有满足选出物品重量之和为 $i$ 的方案的权值和的最大值。
## Sol 4
首先求最大值就不能使用 NTT。相邻的点不能同时选，所以不能启发式合并。
考虑重链剖分，从链低开始考虑，枚举当前点选不选，再递归轻儿子。状态数 $T(n)=\sum_u 2^{u到根轻边数量}$，那么 $T(n)=\max_{a_{1,\ldots,k},a_1 \ge a_i} T(a_1) + 2\sum_{i=2}^k T(a_i)$，发现 $T(n)=n^{log_2 3}$，约等于 $O(n^{1.5}m)$。
考虑若 $m$ 较小的情况，对于大小小于 $B$ 的子树使用上面的做法 $O(\frac{n}{B}B^{1.5})=O(nB^{0.5}m)$。对于大于 $B$ 的子树直接暴力合并，复杂度 $O(\frac{n}{B}m^2)$。$B$ 取 $m^{2/3}$，总复杂度 $O(nm^{4/3})$。
## Pro 5（链分治）
有一棵 $n$ 个点的有根树，第 $i$ 个点有一个重量为 $1$，权值为 $a_i$ 的物品，定义一组选物品的方案的权值为所选物品的权值乘积，要求选的物品对应的点构成一个包含根节点的连通块。求出所有连通块大小为 $i$ 的方案的权值之和。
$n\le 10^5$。
## Sol 5
链分治=树链剖分/全局平衡二叉树+NTT?
全局平衡二叉树一下，记录左端点和右端点是否选了，NTT合并即可？复杂度 $O(n\log^2n)$。
# 长链剖分&树上领域查询
以下的领域查询是基于交换半群的，可以理解为若干数相乘模 $p$ 的结果，$p$ 不一定为质数，，即不能使用逆元。
## 矩阵查询
对于下面的形状的平面，求一个矩阵的信息，但矩阵下面没有边，即矩阵限制为 $a\le x$ 和 $y\le b$。
```
O-O-O-O-O
O-O
O-O-O-O
O-O-O
O
O
```
找到这个矩阵的最小的一个 $x(a\le x)$ 使得 $(x,b)$ 存在点，那么预处理出 $(x,b)$ 左下方的结果，再加上 $[a,x-1]$ 行的结果。
在后面的操作中斜线上的点（即 P）是该链上的点，P 后面跟的是该点的轻子树合并后的结果，那么矩阵查询相当于查询距离某个点 $\le d$ 的点的信息，不过是在子树内的。
```
P-O-O-O-O
P-O
P-O-O-O
P-O-O
P
P
```
## 跳链
考虑询问 $(x,d)$ 为距离 $x$ 小于等于 $d$ 的点的领域。如果 $h_x + 1\le d$（$h_x$ 是 $x$ 所在链的长度），那么 $(fa_x,d-1)=(x,d)$，这样就可以一直跳链。
如果 $z$ 是 $x$ 的第一个满足 $d\le 2h_z$ 的祖先，可以发现在 $x$ 跳到 $z$ 的点 $y$ 之前都满足 $2h_y+1\le d$, 那么 $h_y+1\le d-1-h_y\le d+dep_y-dep_x=d'$。所以满足之前的跳链操作。
那么要解决满足 $d\le2h_x$ 的领域 $(x,d)$，直接对于链顶预处理出该子树外距离 $\le 2h_x$ 的点的信息，发现容易解决，复杂度线性。
如何找到这个点 $z$ 呢？可以找到这个链，然后找到 lca 即可。开 $1\sim n$ 的栈，dfs 时如果遇到链顶则将该点加入 $1\sim h_x$ 的栈中，回溯时再弹出，找到点 $x$ 直接找 $\lfloor d/2\rfloor$ 的栈顶即可。不过这个是离线做法。
### 树上 k 级祖先
考虑 $O(n)-O(1)$ 做法。
$O(n\log n)-O(1)$ 做法瓶颈在于预处理每个点 $\log n$ 个祖先关系，一个点的 k 级祖先可以转化为该子树的一个叶子的祖先？那么可以只预处理叶子的 $\log n$ 个祖先关系，复杂度 $O(lef\log n)$。
对于所有极大的大小小于 $B$ 的子树可以先去掉，剩下的树直接按上面的处理即可，复杂度 $O(\frac{n}{B}\log n)$，对于被删去的树形态最多有 $\frac{\binom B{2B}}{B}$ 种，暴力处理所有形态的树，复杂度 $O(\binom B{2B})$。$B$ 设置成 $\frac{1}{2}\log n\sim \log n$ 比较合适，总复杂度 $O(n)$。
### 序列前驱问题
> 给一个序列 $a_1\ldots a_n$ 和若干询问 $(x,k)$ 求最大的 $y$ 满足 $y\le x$ 且 $k\le a_y$。$S=\sum a_i$，给出 $O(n+S)-O(1)$ 做法。
对于 $i$，建出点 $(i,1)\ldots (i,a_i)$，对于 $(x,y)$ 连向 $(z,y+1)$，$z$ 为存在 $(z,y+1)$ 的最大 $z$，若不存在则为根，那现在建出来一个森林，询问就相当于求 $(x,1)$ 的 $k-1$ 级祖先，直接利用树上 $k$ 级祖先做法即可。
### 在线跳链
直接利用序列前驱问题的做法即可，只不过把序列变成树了。
# Other Problem
## Pro 1
有一棵 $n$ 个点的树，每个点都有一个集合，初始均为空，现在在上面做 $m$ 次操作。第 $i$ 次操作给定 $x_i,y_i$，并将 $x_i,y_i$ 路径上的所有点的集合中都加入 $i$。 然后询问有多少对点满足它们的集合交非空。
$1\le n,m\le10^5$。
## Sol 1
考虑对于覆盖 $i$ 的路径 $x_i,y_i$ 建出虚树，那么虚树大小就是和 $i$ 的集合交非空的点数，对于虚树上的点 $a_1,\ldots a_k$ 按照 dfs 序排序，那么虚树点数就是 $\frac{dis(a_1,a_k)+\sum_i dis(a_i,a_{i+1})}{2}$。复杂度 $O(n\log^2 n)$。
## Pro 2
给定一棵 $n$ 个点的树以及参数 $d$，考虑一个 $n$ 个点的新图 $G$，$G$ 中 $x,y$ 有连边当且仅当 $x,y$ 在原树上的距离 $\le d$。 现在有 $Q$ 次询问，每次询问给定 $l,r$，求只保留 $G$ 中编号为 $[l, r]$ 的点时形成的连通块数量。
$n\le 3\times 10^5,Q\le 6 \times 10^5$。
## Sol 2
考虑使用钦定代表元做法。
按照 bfs 序，将点排列为 $p_1,\ldots,p_n$。考虑到以下性质：
> $x<y<z$，如果 $dis(x,z),dis(y,z)\le d$，那么 $dis(x,y)\le d$。
那么一个连通块的代表元就是排序 $p$ 位置最小的点。求出 $u$ 作为代表元出现的条件 $l\le L \le i \le r$ 中的 $L$，$L$ 可以点分治求出，复杂度 $O(n\log^2 n)$。
## Pro 3
给定一棵 $n$ 个点的树，每个点有一个颜色，有 $Q$ 次查询。查询操作给定参数 $l,r,x$，求只保留编号为 $[l, r]$ 的点之后 $x$ 所在的连通块的不同颜色数。
$n,Q\le 10^5$。
## Sol 3
直接点分治，查询当前根是否在 $x$ 的连通块内，如果在直接询问，2-side 矩形数颜色即可。$O(n\log^2n+Q\log n)$。
## Pro 4
给定一棵 $n$ 个点的树，有 $Q$ 次询问，每次给定 $l, r, x$，求有多少对 $(i, j)$ 满足 $l \le i < j \le r$, $lca(i, j) = x$。
$n,Q\le 2\times 10^5$。
## Sol 4
大致的计数思路可以是 $|S-\cup_{l\le i \le r}i\notin tree_x|^2-\sum_{v\in son_x} |S\cap tree_v|^2$ 。
如果 $d_x\le \sqrt n$，直接暴力枚举儿子，然后二维数点即可，数一次复杂度是 $O(1)$ 的。
否则先处理前 $\sqrt n$ 大的子树，那么剩下子树的点考虑提前预处理出来，按照点编号排序，对于在不同子树的点给它们染色即可，那么可以变成一个莫队处理即可。发现每个点只会出现在一个祖先的处理序列里面，所以总复杂度 $O(n\sqrt n)$。
## Pro 5
给定一颗大小为 $n$ 的有根树，每个点有权值 $a_i,b_i$，每个点的父亲都小于当前点编号。定义一个点的 $c$ 值为其所有没被标记的儿子的 $b$ 值加上该点的 $a$ 值。初始整棵树的点都没被标记，每次计算出所有点的 $c$ 值，然后选择没被标记的点中 $c$ 值最大的那个并标记，如果有多个则取编号最大的。
现在有 $Q$ 次操作，每次询问形式为如下两种之一：
- 给定 $x, A, B$，更改 $x$ 的 $a, b$ 值为 $A, B$。
- 给定 $x, y$，询问如果进行题目中所描述的标记过程，问 $x$ 是否比 $y$ 先被标记。
$1\le n,Q\le 2\times 10^5,1\le a_i,b_i\le10^8$。
## Sol 5
考虑维护 $g_u$ 为当点 $u$ 被标记时它的 $c$ 值，一个点的 $g_u$ 只于 $b_{son_u}$ 和 $g_{son_u}$ 有关，可以搞个权值线段树维护这个东西。暴力修改复杂度 $O(\sum dep\log V)$。
可以重链剖分，对于一条链维护线段树，对于一个区间 $[l,r]$ 维护 $f_{0/1},p$，$f_{0,1}$ 为 $r$ 的重儿子比 $r$ 先/后选时 $g_l$ 的值，$p$ 为 $r$ 的重儿子比 $r$ 后选 $g_r$ 的值。复杂度 $O(n\log n\log V)$。