基环树

· · 个人记录

算法

基环树，指 n 点 n 边的图。

基环树森林，指每棵树都是点数和边数相等。

容易发现，基环树和普通的树只有一条边的差别，普通的树是 n-1 条边。基环树加了一条边，而这一条边一定会在树上形成一个环。

对于此类题目，解决方法如下：

找环

考虑并查集。当边上的两点祖先相同，则说明这是环上的两个点。

根据这两个点，搜索之前的边，找到环上的所有点。

不难看出，有向图和无向图都适用。

namespace Fring {
    int fa[N], S, T;
    int find(int x) { return (fa[x] == x ? x : fa[x] = find(fa[x])); }
    bool mksure(int x, int fa) {
        if(x == T) {
            G[sum].pb(x); vis[x] = 1;
            return 1;
        }
        for(int i = 0;i < g[x].size(); ++i) {
            int to = g[x][i].u;
            if(to == fa) continue ;
            if(mksure(to, x)) {
                vis[x] = 1;
                G[sum].pb(x), V[sum].pb(g[x][i].w);
                return 1;
            }
        }
        return 0;
    }
    void Two() {
        for(int i = 1;i <= n; ++i) fa[i] = i;
        for(int i = 1;i <= n; ++i) {
            int x = find(X[i]), y = find(Y[i]);
            if(x == y) {
                S = X[i], T = Y[i];
                ++sum;
                mksure(S, 0);
                V[sum].pb(Z[i]);
            }
            else fa[x] = y;
        }
    }
}

也可以根据 tarjan 的性质搜索。考虑将点放入栈，搜到返租边则取出栈中元素得到所有环上的点。

void tarjan(int x, int f) {
    dfn[x] = ++cnt;
    st.push(x);
    for(auto &to : G[x]) {
        if(!dfn[to]) {
            fa[to] = x;
            tarjan(to, x);
        }
        else if(to != f) {
            for(int i = x;i != to;i = fa[i]) ans[++num] = i; 
            ans[++num] = to;
        }
    }
}

例题

骑士

没有上司的舞会，不过从树变成了基环树。

首先，如果是一棵树，我们可以根据树形 DP 直接解决。大致的思路是定义 dp_{x,0/1} 表示选 x 与不选 x 的最大值。有状态转移方程：

dp_{x,0}=\sum_{to} \max(dp_{to,0},dp_{to,1}) ,\ dp_{x,1}=a_x+\sum_{to} dp_{to,0}

我们考虑转换成树。首先找到环，以及环上任意的两个相邻的点。将两点之间的这条边删掉，就变成了一棵树。以这两个环为根分别求树的直径取答案最大值。

每次到达环上点 x 时，下一步必然不能是与之相连的点 y。于是这样求是正确的。

最后，每个环只用两个相邻点就可以了，因为根据相邻不选的性质可以推出其它点的结果是一样的。于是时间复杂度就是树形 DP 的 O(n)。

Island

求基环树的最大直径。

首先找出环，先考虑直径不包含环点的情况，即以每个环点为根节点，向下求其子树的直径（不能走到环上）。容易发现，这种情况是可以独立的。可以直接树形 DP，记录最大值和次大值即可。

然后考虑环上的情况。从环上一点 x 到 y，我们要计算的就是 x 和 y 的子树的包含 x 的最长直径，以及 x 和 y 之间的环上距离之和。

设 d_x 为 x 子树中包含 x 的最长直径，s_x 为环上 [1,x] 点的距离。容易发现 d_x 就是第一种情况的包含 x 的直径。对于两点 (x,y)\ \ (y>x)，要求：

d_x+s_y-s_x+d_y

然后把 x 和 y 分别放一边：d_x-s_x+s_y+d_y（y 为我们枚举的点，x 为需要维护的点）。

假设我们枚举 y，那么 s_y+d_y 就是定值，只需维护 d_x-s_x\ (x<y) 的最大值。可以单调队列。

设环长为 m，则遍历 y 的耗时为 O(m)，而环上的每一个点都要向其子树作树形 DP，时间是其子树的长度，加起来一共是 O(n-m)，所以总共的时间复杂度为 O(n)。

Rendezvous

找出 x 和 y 使得 a 向上走 x 步和 b 向上走 y 步到同一个点。

首先考虑无解的情况，当且仅当 x 和 y 根本不在同一基环树上时无解。

然后思考两点的位置关系，显然如果都不经过环，即都是环上一点的子树上的点，那么就是正常的树上 LCA。求出 x 和 y 的 LCA u，设 dep_x 表示 x 在树上的深度，则 x 要走 dep_x-dep_u，y 要走 dep_y-dep_u，如果要边 x 和 y 的话，只能是同时往上走，即都增加 \Delta，不满足条件 2。

还剩两点都在环上，以及一点在环的子树上，两点都在不同环点的子树上的问题。

首先，我们需要将这些非环点向上刚好走到环上（他的根节点），设分别走 p_x 和 p_y 步。然后就转变为了求两点都在环上的问题了。

然后因为是有向图，所以环也是有方向的。设 x 和 y 在环上的位置为 i 和 j，环的长度为 m。分类讨论：

然后，根据题目给出的性质，判断是从 x 到 y 还是从 y 到 x，即 (p_x+dis_{x,y},p_y) 还是 (p_x,p_y+dis_{y,x}) 。有点麻烦，但是不难。

一个可能会影响思考的点是，点 a 和 b 可以在环上绕来绕去的，但这不满足条件 2，所以只会相遇，然后停止。

旅行

你可以在环上遍历到一半中途回溯一次。最终使遍历到的点组成的序列的字典序最小。

首先我们要使 x 向下的遍历顺序为从小到大，如果用邻接表存储就可以排序。

然后 60 分白送。

思考是基环树怎么做。

观察数据范围，O(n^2) 可过。于是仿照第一题，将环上的边一一删掉，然后转换为前 60 分。

但是能，此题有加强版告诉我们，有 O(n\log n) 的做法。

\color{white}{~~但是我还没搞懂~~}

Roads in the Kingdom

和 Island 相似。

“需拆除一条道路并同时要求所有城市仍然联通” 说明这条道路一定在环上。

设当前短的边为 (i,i+1)，分类讨论直径在环上的出现位置：

前两个可以用单调队列，但是我不想用。

于是递推，感觉情况比单调队列更复杂。

回顾 T2 中的这个式子 d_x-s_x+s_y+d_y（y 为我们枚举的点，x 为需要维护的点），其实并不用单调队列。因为没有区间范围限制，考虑用一个变量 cnt 维护 d_x-s_x 最大值，将 1\rightarrow x 的最大值记为 l1_x，则 l_x=\max(l_{x-1},s_x+d_x+cnt)。

右边的情况同理，不过因为方向反了，所以式子变化成了 d_x+s_x-s_y+d_y\ (y<x)。稍微改改即可。

然后 1 和 2 的情况就出来了。考虑 3。

直接给式子。d_x+d_y+s_x+(s_m-s_y)，应该不难理解。我们可以求出 L_i=d_x+s_x 和 R_i=d_y+(s_m-s_y)，然后对应的答案就是 L_{i-1}+R_i。

所以最后的答案为 \max(l_{i-1},r_i,L_{i-1}+R_i)。最后不要忘了，和 T2 一样，直径不在环上的情况。