• 周日. 11月 27th, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

基 础 树 上 问 题

admin

11月 28, 2021

即luogu题单【图论2-1】基础树上问题
这份题单难度还是非常大的。所以这里就是对题单中10道题的简单讲解。
之后会再发一篇NOIP TG/CSP-S中树论题目的讲解,那篇的难度可能还会再大一些(咕咕咕

感谢luogu题解和《算法竞赛进阶指南》提供部分题目思路。

前置知识:树的直径和重心,LCA。
以下题目按照luogu上的难度排序。代码不放了(懒

1. [USACO19DEC]Milk Visits S

简明题意:树上的每个结点都是黑白两种颜色之一,每次询问一条链上是否有某种颜色。

思路:
一道简单的套路题……
两种颜色可以分开讨论,每次关注一种颜色即可。
加强一下这道题,改成询问一条链上某种颜色结点的个数。
dfs预处理出树上结点到根节点的路径上某种颜色结点的个数,不妨记为(dep[u][color])
于是答案就是(dep[u][color]+dep[v][color]-dep[lca][color]-dep[father[lca]][color]),做完了。
时间复杂度(O(nlog n))

2. 会议

简明题意:给定一棵边权为1的无根树,找出一个结点,使得其他结点到该结点的距离和最小,且编号最小。

思路:
你需要知道一个结论:树的重心到树上其他节点的距离和最小。
于是这道题就做完了(笑
当然更普适的做法是换根dp,这里不予讨论。
时间复杂度(O(n))

3. 【模板】最近公共祖先(LCA)

略。

4. 【XR-3】核心城市

题意:
给定一棵边权为1的无根树,选取 (k) 个特殊结点,使:

  1. 这些点两两可不经过非特殊结点而相互到达。
  2. 非特殊结点到其最近的特殊结点的距离的最大值最小。求出这个最小值。

思路:
个人认为从反方向考虑更加简单一些。
显然有这样的思路:每次都将树的叶子结点删去,直至树中剩余结点数量为 (k)
类似于拓扑排序,我们可以通过队列来模拟。
因为树的边权都为1,可以证明这样做的正确性。
还有一个问题:如何计算最终的答案?
可以这样想:特殊结点到这个点的距离,就是这个点到特殊结点的距离。(废话
于是我们可以对每个结点定义一个(d[u]),初始化为1。
每次删除叶子节点时,用它们的(d)值更新新的叶子结点的(d)值,
具体地,若有结点(u)为叶子结点,(v)为一个与它相邻的新的叶子结点,则有(d[v]=d[u]+1)
最后队列里剩下的(d)值就是答案了。时间复杂度(O(n))

5. [NOIP2007 提高组] 树网的核

简明题意:
给定一棵带权无根树,在其直径上找到一段长度不大于(s)的链(称为核,可退化为一个点),使得树上的其他结点到该路径距离的最大值(称为偏心距)最小。

我们发现原题里数据范围是(nleqslant 300),但实际上我们可以做到(O(n))
思路:
我们需要一些结论:

  1. 每一条直径求出的最小偏心距都是一样的,因此我们可以任选一条直径进行计算
  2. 直径是树中最长的链(废话

接下来我们随便找一条直径(D),记其端点分别为(l)(r)
接下来对直径上的每个点(u)求出到不经过直径能达到的最远的点的距离,记其为(d[u])
然后记选取的核(C)两端分别为(x)(y)。接下来我们计算偏心距(E)
因为直径是最长的链,所以(x)所能到达的最远点是(l)(y)所能到达的最远点是(r)
于是我们可以这样计算偏心距:
(E=max{max_{uin C}{d[u]},dis(l,x),dis(y,r)})
然后我们发现内层的那个(max)并不好处理。
但是因为直径是树中最长的链,我们有下列性质:
对于链((l,x))上任意一点,其(d)值不会大于(dis(l,x))((y,r))的情况同理。
这是因为若有(d[u]>dis(l,x)),此时记(p)满足(dis(u,p)=d[u]),则(x-u-p)(x-u-l)更长。
显然这是不可能的,于是我们可以将链((l,x))和链((y,r))上点的(d)值也算上,一起取(max),而不会有任何影响。
则原式变成了(E=max{max_{uin D}{d[u]},dis(l,x),dis(y,r)})
显然(max_{uin D}{d[u]})这一项可以预处理出来。
但这还不够,我们需要富有智慧地枚举((x,y))
方法是这样的:我们从直径的端点开始依次枚举点(x)。对于每个(x),将(y)向右移动直到链的长度最大,并用上面的式子更新一次答案。
看上去时间复杂度不是很正确,但是我们分析,(x)(y)都最多移动(n)次,枚举的时间复杂度实际上是(O(n))
最终我们就以(O(n))的时间复杂度解决了这道题。

6. 仓鼠找sugar

简明题意:多次判断树上的两条链((a,b))((c,d))是否有交点。

思路:
简便起见,记(f)(lca(a,b)),记(g)(lca(c,d))
然后就是暴力分类讨论。不妨设(dep[f]leqslant dep[g])

  1. (dep[f]=dep[g]):显然只有(f=g)时两条链才能重合。
  2. (dep[f]<dep[g])
    这个时候两条链重合当且仅当(a,b)中有一点在(g)所在子树内。
    这等价于(lca(a,g)=g)(lca(b,g)=g)

于是就做完了。

7. [AHOI2008]紧急集合

简明题意:边权全部为1的无根树上有(a,b,c)三点(可重合),找到一个点(p)使得到这三个点的距离最小,并求出这个最小值。

思路:
注意到三个点中必然有至少两对点的LCA是相同的。显然集合点应取重合的LCA处。
计算距离的方法同第一题,最终会发现都是 (dep[a]+dep[b]+dep[c]-dep[lca1]-dep[lca2]-dep[lca3])

8. 小猪佩奇爬树

9. [APIO2010]巡逻

10. [CSP-S2019]树的重心

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注