10-05 树杂题 笔记

感觉罗大神两天讲题的听课体验都挺好的啊

今天最后两题有点神仙，暂时还没放上来，完全消化了再填坑吧

「CF911F」

Description

给定一棵 $n$ 个节点的树，你可以进行 $n - 1$ 次操作，每次操作步骤如下：

• 选择 $u, v$ 两个度数为 $1$ 的节点。
• 将 $u, v$ 之间的距离加到 $ans$ 上。
• 将 $u$ 从树上删除。

求一个操作序列使得 $ans$ 最大。

Solution

先把直径拿出来，将直径外的点一个一个的和直径中的某一个端点配对并删掉。最后再将直径删掉。

这个做法显然是对的。。。

「CF1051F」

Description

给定一张$n$ 个点 $m$ 条边的带权无向联通图，$q$ 次询问，每次询问 $u_i$ 到 $v_i$ 的最短路长度。

$n, q \le 10^5 , m - n \le 20$

Solution

首先随便搞一棵生成树，把这些非树边边的端点标记为特殊点。

对于每一个询问，如果最短路只经过生成树上的边，就可以直接计算。

否则一定经过了一个特殊点，把所有特殊点预处理出最短路，然后枚举这个特殊点，然后更新答案就行了

「CF1042F」

Description

给定一棵 $n$ 个节点的树，定义叶子是度数为 $1$ 的节点，点集 $S$ 是好的如果满足任意两个 $S$ 中的点之间的距离 $\le k$

现在要求将所有叶子分成若干不相交的好的集合，请问最少分成多少个好的集合。

$n, k \le 10^6$

Solution

先随便选一个不是叶子的根，然后可以自底向上贪心。

设 $f_p$ 表示 $p$ 为根的子树内已完成的好的集合的数量，$g_p$ 表示未完成的集合中离 $p$ 最远的叶子的距离。

（实际上这里指的未完成的集合是指集合内距离都$\le k$，如果大于$k$则必须再新加入一个集合）

考虑如何计算

首先将所有儿子的 $f$ 先求和，然后将所有儿子的 $g$ 排序，不断检查 一下最大的 $g$ 和次大的 $g$ 相加是否大于 $k$，如果大于，那么就将最大的 $g$ 删掉， 并把 $f_p$ 加上 1，循环过程。否则就令 $g_p$ 等于最大的 $g$ 加 $1$并跳出。

「CF1025D」

Description

给定$n$ 个节点，每个节点上有一个数字，要求用这些节点构建一棵二叉搜索树，满足有边相邻的两个节点上的数字互质。

$n \le 600$

Solution

先排序，考虑Dp

设 $f[i][j][k]$ 表示第 $i$ 个点到第$j$ 个点，以 $k$ 为根是否可行。

转移的时候查看是否存在 $u \in [i, k - 1]$ 满足$f[i][k - 1][u] = 1$ 且 $u$ 上的数字和 $k$ 上 的数字互质，右边类似。

这样就是 $O(n^4 )$ 的。 注意到上面的做法有一些重复运算。

于是设$L[i][j]$表示是否存在 $k \in [i, j]$ 满足 $f[i][j][k] = 1$且 $k$ 上的数字和$j + 1$上的数字互质，类似地定义 $R[i][j]$

于是复杂度就被降为 $O(n^3 )$

「CF955F」

Description

给定一棵以 $1$ 号点为根的树。若满足以下条件，则认为节点 $p$ 处有一个 $k$ 叉高度 为 $m$ 的堆：

• 若 $m = 1$，则 $p$ 本身就是一个 $k$ 叉高度为 $1$ 的堆。
• 若 $m > 1$，则 $p$ 需要有至少 $k$ 个儿子满足在儿子处有一个 $k$ 叉高度为 $m - 1$ 的堆。

令 $dp[k][p]$ 表示在 $p$ 处 $k$ 叉堆的最大高度，求 $\sum_{i=1}^{n} \sum_{j=1}^{n} dp[i][j]$

$n \le 3 * 10^5$

Solution

如果固定 $k$，求所有的 $dp[p][k]$ 只需要dfs 整棵树，对于某个点 $p$，若其子节点数 $< k$，则 $dp[p][k] = 1$，否则 = 子节点 的 dp 值中第 $k$ 大的值 $+1$ 。运用 nth_element 可以做到 $O(n)$。这样总复杂度就是 $O(n^2 )$

观察到对于 ，有 ，所以可以考虑对 值分段计算。

设 $f[p][x]$表示满足 $dp[p][k] \le x$ 的最大的 $k$。

$f$ 只有 $n\log(n)$ 个状态，计算 $f$ 的时间复杂度是 $O(n\log^2 (n))$，计算出 f 后就可以轻松得到答案了。

来历不明的题

Description

给定一棵 $n$ 个点的带边权树，$m$ 次询问，每次询问给出两个值 $p, k$，求以下值：

$\sum_{q| dis(p,q)\le k} dis(q, p)$

Solution

动态点分治（点分树）裸题

首先点分治，把分治结构建好。

每个分治中心要记录当前分治区域所有点到分治中心的距离，以及分别记录每个分 治子区域中的所有点到分治中心的距离，以及当前分治中心到其分治祖先的距离。

每次查询时在每个分治中心根据以上信息查询就可以了。