• 周一. 5月 27th, 2024

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]树的重心

《基 础 树 上 问 题》有一个想法
  1. Wow, wonderful weblog structure! How lengthy have you ever been blogging for?
    you made blogging look easy. The full look of your site is
    magnificent, let alone the content! You can see
    similar here sklep online

发表回复

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