【学习】基环树

2018/07/15 21:00
阅读数 10

基环树,也是环套树,简单地讲就是树上在加一条边。它形如一个环,环上每个点都有一棵子树的形式。因此,对基环树的处理大部分就是对树处理和对环处理。显然,难度在于后者。

扣环

这是几乎所有基环树处理的第一步。扣环的方法多种多样,各有千秋,反正都是$O(n)$的。这里贴一下本人扣环的代码。这个东西,稍微博采众长一下就好了。

struct edge {
  int la,b,v;
} con[N << 1];
int tot, fir[N];
int vis[N], cnt, lop[N], dist[N], inl[N], rt;
int getlop(int pos,int fa) {
  if (vis[pos]) {
    rt = pos;
    return 1;
  }
  vis[pos] = 1;
  int tmp;
  for (int i = fir[pos] ; i ; i = con[i].la) {
    if (con[i].b == fa) continue;
    if (tmp = getlop(con[i].b,pos), tmp) {
      if (tmp == 1) {
		lop[++cnt] = pos;
		dist[cnt] = con[i].v;
		inl[pos] = 1;
		if (pos != rt) return 1;
      }
      return 2;
    }
  }
  return 0;
}

<br>

接下来就是题目了。

<br>

BZOJ1791 Island

题意:有一个基环树和树组成的森林,共有$n$个结点,边有边权。试求其中所有联通块的直径之和。

$n \leq 10^6$

我们只用考虑如何求出一个基环树的直径。

首先,我们要对环上所有点的子树求出它们的直径和最大深度。然后,我们只用考虑在环上至少经过一条边的路径。那么,这种路径在环上一定有起始点和终点。(假设路径是从起始点开始,按顺时针方向走达到终点)

不妨枚举这段路径在环上的终点。由于规定了这个点和方向,我们就可以拆环了。然后是一个经典的技巧,把环上元素复制一遍,就可以枚举全部拆环方案。设环上有$l$个结点。那么,我们枚举终点,就相当于在长度为$2l$的数组上不断滑动一个长度为$l$的区间。

剩下的问题与基环树已经没什么关系了。设环上边权的前缀和为$sum$,环上结点的子树的最大深度为$dep$,那么,在环上起始点为$i$,终点为$j$的路径能得到的长度就是$sum_j - sum_i + dep_j + dep_i$。既然枚举了$j$,我们在滑动区间时就只用维护$dep_i - sum_i$的最大值就可以了。这个可以用单调队列实现。

时间复杂度$O(n)$。

<br>

CF835F. Roads in the Kingdom

题意:有一棵$n$个结点的基环树,边有边权。需要从环上删去一条边,以最小化直径。输出最小化后的直径。

$n \leq 2 \times 10^5$

本题和上道题类似,做法也相近。我们只用枚举删掉的是哪一条边,然后因为路径长度是$sum_j+dep_j-sum_i+dep_i$,我们用两个set维护所有$sum_i+dep_i$和$-sum_i + dep_i$。这样就能求直径只要从两个set中分别取出最大值就好了。当然,还要特判两个最大值是同一个结点的情况。

时间复杂度$O(n \log n)$。

<br>

BZOJ2878 迷失游乐园

题意:有一棵$n$个结点的基环树,边有边权。当你从一个结点出发后,你每次会等概率地选择下一个未被访问过的结点,并走到那个结点,直到与当前点相邻的结点都被访问过为止。试求等概率选择出发点,所走的路径长度的期望值。

$n \leq 10^5$

先考虑如何对树做这个问题。我们设$dp_i$为从结点$i$开始,只向孩子结点走的路径的期望长度。按照题意可以得到$dp_i = \frac {\sum_{j \in ch_i} dis(i,j) + dp_j} {|ch_I|}$。在计算出所有$dp$值后,再从父亲向孩子结点更新,得到每个点的答案。这样,就是两遍树形dp,一次从下往上更新,一次从上往下更新。

然后考虑对环的处理。环上的两个结点互相到达,既可以按顺时针方向走,也可以按逆时针方向走。因此,我们枚举这个方向,就可以拆环了。然后,我们可以用类似的方法,求出环上结点之间的贡献。这里特别提及一个细节,当在环上向右移动区间时,我们不但要删去区间旧左端点的贡献,还要考虑新左端点因为成为边界,不能再向左走,其贡献会增加。更确切地说,设旧左端点为$u$,新左端点为$v$,那么,原来对于$v$的,有$\frac {1} {|ch_v| + 1}$的可能向$u$走,但现在,就只有向它的子树走的可能了,故$v$的贡献会改变。

这样,通过一次dfs,两次环上处理,再加一遍dfs,就能解决本题。

时间复杂度$O(n)$。

<br>

上面的问题中,我们可以直接拆环,把环上元素复制一遍来解决。然而,对于另一些问题,我们需要使用枚举环端点元素的状态的技巧,以实现破环成链。

<br>

BZOJ1040 骑士

题意:有一个基环树森林,含有$n$个结点。求其带权最大独立集。

$n \leq 10^6$

关于如何求树的带权最大独立集,这里便不必赘述了。

考虑处理环,我们枚举其中某个元素选还是不选,就能破环成链了。

时间复杂度$O(n)$。

<br>

ARC079F - Namori Grundy

题意:有一个弱联通的有向图,含有$n$个结点和$n$条边。试问是否存在方案,赋给每个结点一个自然数权值$val_i$,满足对于所有结点$u$,$val_u = {\rm mex}{val_v | (u,v) \in E}$。一个集合的$\rm mex$是没有在这个集合中出现的最小自然数。

$n \leq 2 \times 10^5$

唯一能导致无解情况出现的就只有环了。我们扣环之后,对环上所有结点的外向树做dfs,这样就只用考虑环了。

顺便一提,对于所有已知${val_v | (u,v) \in E}$的结点$u$,$val_u$直接暴力求就可以了。设$a_i$表示$val_u = i$时,以$u$为根的外向树中最少需要的结点数(包括$u$)。那么,可以得到:

  • $a_0 = 1$
  • $a_i = \sum_{k=0}^{i-1} a_i + 1$

对这个数列求通项,得到$a_i = 2^i$。因此暴力求$\rm mex$是$O(\log n)$的。

设$S_u$表示${val_v | (u,v) \in E}$,那么,对于环上所有结点$u$,$val_u$要么是${\rm mex} S_u$,要么是$S_u$中没有出现的次小的自然数。后一种情况会出现当且仅当$u$在环上前一个结点的权值恰好等于${\rm mex}S_u$。于是,我们枚举环上某一个结点是上面哪一种情况,在环上扫一遍判断一下就好了。

时间复杂度$O(n \log n)$。

<br>

小结:总算是对基环树有一个初步的了解。上面例题虽然涉及的做法比较单一,但能反映出基环树的问题大部分上就是树和环,而环又通常转化为链来处理。当然,也必然存在其他新颖的做法。而要丰富自己的认识,估计就只能靠见识更多的题目了。

展开阅读全文
mex
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部