0. 前言

你需要的知识点：

图的遍历与存储（这都会吧。。。）
树的直径与树上最大独立集（没有上司的舞会）等树形DP基础芝士
环的认识

1. 基环树基本芝士

1.1 概念

想必都知道树结构的特点吧。

给定一张 $n$ 个点， $n-1$ 条边的无向图，…

这个就是树的特点，有 $n-1$ 条边。而基环树呢？就是在原先树的情况上加了一条边，于是基环树的特点就是：

给定一张 $n$ 个点， $n$ 条边的无向（或有向）图，…

那长什么样？

那有人就会说链，这根本就不是树啊，这有环怎么能叫树呢？事实上也是这样的，人家是个图吗。

比一般的树多一条边，这导致这个基环树图上出现了一个唯一的环，这个的前提是图联通。如果不联通，就会出现多个环，例如下图：

当然，基环树也有有向图的版本，这个版本有2个，一个叫内向基环树，一个叫外向基环树。

1.2 找环

我们对于基环树的处理一般是找到他最特殊的地方，也就是他的环。

怎么找环呢？其实也很简单，我们分无向的和有向的来分别说。

1.2.1 并查集（无向图）

复杂度均摊 $O(1)$ 。

无向图我们可以使用并查集来判断联通性，这也是找环的一个方法。我们在读取边的时候就可以使用并查集判断，如果发现 $u,v$ 的并查集节点一致，那么他们互相联通，已经成环，此时 $u-v$ 组成的边就是环边的一部分，也就是那一条加入的非树边。

int n,pre[MN];
vector<int> adj[MN];

int root(int x){
    if(x==pre[x]) return x;
    else return pre[x]=root(pre[x]);
}

void init(){
    for(int i=1;i<=n;i++){
        pre[i]=i;
    }
}

int main(){    
    cin>>n;
    init();
    for(int i=1;i<=n;i++){
        int u,v;
        cin>>u>>v;
        int ru=root(u),rv=root(v);
        if(ru==rv){
            cir.push_back(pir(ru,v));// 找到环边
            continue;
        }else pre[rv]=ru;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    return 0;
}

1.2.2 拓扑排序（无向图）

复杂度 $O(n)$

一个显然的想法就是将无向图转化成有向图去做，把无向图转化成两条有向边，当一个节点的入度大于等于2时，点在环上。用的不算太多，不给出代码了。

1.2.3 LCA (无向图)

复杂度 $O(n)-O(n\log n)$

显然？只需要找到最短路径即可，但是没太大啥用。

1.2.4 DFS序（无向图）

复杂度 $O(n)$

这需要我们记录2个变量： $dfn,fa$ ，分别代表DFS序（时间戳）与父亲节点编号。

不难发现如果我们下一个访问的节点已经被访问过，说明已经成环，我们可以借助这个来实现找环。

void dfs(int u,int pre){
    dfn[u]=++tot;
    fa[u]=pre;
    for(auto v:adj[u]){
        if(v==pre) continue;
        if(dfn[v]){
            if(dfn[v]<dfn[u]) continue; // 为什么这里continue？
            lp[++htot]=v;
            for(;v!=u;v=fa[v]) lp[++htot]=fa[v];	
        }else dfs(v,u);
    }
}

有些人会对if(dfn[v]<dfn[u]) continue;这一句感到疑惑，为什么要这么搞？
仔细思考，当dfn[v]<dfn[u]时其实就是 $v$ 是 $u$ 的祖先节点（不是父亲节点），这个其实就是返祖边，如果我们只靠返祖边来判断环肯定是不对的，我们需要跳过所有祖先节点，避免跨代误判。如果去掉，则会出现路径记录不全的情况，甚至会将树边误判为环边。

1.2.5 自底向上（有向图）

有向图最简单的算法，不需要太多解释，你发现有个节点之前被访问过那么肯定成环：

int getlp(int u){
    vis[u]=1;
    if(vis[fa[u]]) return u;
    else return getlp(fa[u]);
}

1.3 基环树问题解法

问题解法有哪些呢，一般来说我们有2个思想（计数的滚出去(#`Д´)ﾉ）：

借鉴环形DP两次DP，在环一个位置强制断开（或忽略）成树跑一遍计算答案。第二次通过适当的改动算出的答案等价于把断开的边强制相连。
把基环树的环给提起来，这样提起来的树换上的节点挂着一个一个对应的子树，先算子树的答案，在合并到环上的节点，最后就变成链环上问题。例如下图：

2. 基环树的例题

2.1 基环树直径——洛谷P4381

基环树的直径指基环树中最长的简单路径被称为基环树的最长链，其长度就是基环树直径。

基环树的直径的答案可能出现在2个位置：

单个子树中（不跨环）
跨子树（跨环）

我们利用第二个方法：
先找出基环树的环，让后先对环上的节点跑树形DP求树的直径，记为 $D_i$ 。

对于答案1，即为 $ans1=\max\limits_{i=1}^{len} D_i$ ，其中 $len$ 为记录的环节点个数（即环长）。

而对于跨子树，答案即为：

f[i]=\max\limits_{j=1,j\neq i}^{len} D_i+D_j+dis(i,j)

对于 $dis(i,j)$ ，有逆时针和顺时针两种走法，走最长的。

$O(n^2)$ 有点炸裂，而且环不好处理，我们可以考虑一个环形DP最常用的方法，断环复制1分。让后因为 $D_i$ 是定值可以提出来。

不难有：

f[i]=D_i+\max\limits_{j=1}^{i-1} D_j+dis(i,j)

到这里还看不出来怎么优化的（没学过没关系可以看我的DP优化博客)，这不就是最标准1D/1D单调队列优化模型吗？复杂度 $O(n)$ 结束。

但是原题其实是个基环树森林，每一次统计一遍答案就可以了。

当然，还记得我们提到的那个小可爱二元环吗，那个需要特判，在大部分题中作为一个普遍的hack数据出现，请大家特别注意。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
constexpr int MN=1e6+15;
struct Edge{
    int v,w;
};
int n,len,fa[MN],dfn[MN],tot,lp[MN];
ll d[MN];
vector<Edge> adj[MN];
ll q[MN<<1],s[MN<<1],ql,qr,anszj;
bool vis[MN];

void dfs(int u,int pre){
    dfn[u]=++tot;
    fa[u]=pre;
    for(auto e:adj[u]){
        if(e.v==pre) continue;
        if(dfn[e.v]){
            if(dfn[e.v]<dfn[u]) continue;
            lp[++len]=e.v;
            for(;e.v!=u;e.v=fa[e.v]) lp[++len]=fa[e.v];	
        }else dfs(e.v,u);
    }
}

void getzj(int u,int pre){
    vis[u]=1;
    for(auto e:adj[u]){
        if(e.v==pre||vis[e.v]) continue;
        getzj(e.v,u);
        anszj=max(anszj,1ll*d[u]+d[e.v]+e.w);
        d[u]=max(d[u],d[e.v]+e.w);
    }
}

ll solve(int rt){
    ll ans1=0,ans2=0;
    len=tot=0;
    dfs(rt,0);
    lp[0]=lp[len];
    for(int i=1;i<=len;i++){
        vis[lp[i]]=1;
    }
    for(int i=1;i<=len;i++){
        anszj=0;
        getzj(lp[i],0);
        ans1=max(ans1,anszj);
    }
    if(len==2){// 特判小可爱
        for(auto e:adj[lp[1]]){
            if(e.v==lp[2]) ans2=max(ans2,1ll*d[lp[1]]+d[lp[2]]+e.w);
        }
        return max(ans1,ans2);
    }
    for(int i=1;i<=len;i++){
        for(auto e:adj[lp[i]]){
            if(e.v==lp[i-1]){// 考虑前缀和优化dis计算
                s[i]=s[i-1]+e.w;
            }
        }
    }
    for(int i=1;i<=len;i++){// 复制
        s[len+i]=s[len]+s[i];
    }
    ql=1,qr=0;
    q[++qr]=0;
    for(int i=1;i<=len*2;i++){
        while(ql<=qr&&q[ql]<=i-len) ql++;
        ans2=max(ans2,d[lp[q[ql]%len]]+d[lp[i%len]]+s[i]-s[q[ql]]);
        while(ql<=qr&&s[q[qr]]-d[lp[q[qr]%len]]>=s[i]-d[lp[i%len]]) qr--;
        q[++qr]=i;
    }
    return max(ans1,ans2);
}

signed main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        int v,w;
        cin>>v>>w;
        adj[i].push_back({v,w});
        adj[v].push_back({i,w});
    }
    ll ans=0;
    for(int i=1;i<=n;i++){
        if(!vis[i]) ans+=solve(i);
    }
    cout<<ans;
    return 0;
}

2.2 基环树找环洛谷P8655

无向图找环，可以作为试验场。记得排序后输出。

#include<bits/stdc++.h>
using namespace std;
constexpr int MN=1e6+15;
int n,dfn[MN],lp[MN],fa[MN],htot,tot;
vector<int> adj[MN];

template<typename type>
inline void read(type &x)
{
    x=0;bool flag(0);char ch=getchar();
    while(!isdigit(ch)) flag=ch=='-',ch=getchar();
    while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    flag?x=-x:0;
}

void dfs(int u,int pre){
    dfn[u]=++tot;
    fa[u]=pre;
    for(auto v:adj[u]){
        if(v==pre) continue;
        if(dfn[v]){
            if(dfn[v]<dfn[u]) continue;
            lp[++htot]=v;
            for(;v!=u;v=fa[v]) lp[++htot]=fa[v];	
        }else dfs(v,u);
    }
}

int main(){
    read(n);
    for(int i=1;i<=n;i++){
        int u,v;
        read(u);
        read(v);
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs(1,0);
    sort(lp+1,lp+1+htot);
    for(int i=1;i<=htot;i++) cout<<lp[i]<<" ";
    return 0;
}

2.3 无向基环树最大独立集洛谷P2607

相互厌恶的骑士之间建无向边，但是没说联通，是基环树森林。

其实我们想跑没有上司的舞会，但是因为不是树不好做，我们用第一种方法，强制不选，另外一个随便。这样就可以分别统计了。

#include<bits/stdc++.h>
#define ll long long
#define pir pair<int,int>
using namespace std;
const int MN=1e6+15;
struct circle
{
    int u,v;
};

struct edge{
    int v,id;
};
int n,pre[MN];
ll val[MN],f[MN][2];
vector<edge> adj[MN];
vector<pir> cir;

int root(int x){
    if(x==pre[x]) return x;
    else return pre[x]=root(pre[x]);
}

void init(){
    for(int i=1;i<=n;i++){
        pre[i]=i;
    }
}

void dfs(int u,int fa){
    f[u][0]=0;
    f[u][1]=val[u];
    for(auto e:adj[u]){
        int v=e.v,id=e.id;
        if(v==fa) continue;
        dfs(v,u);
        f[u][1]+=f[v][0];
        f[u][0]+=max(f[v][0],f[v][1]);
    }
}

int main(){
    ios::sync_with_stdio(0);
    cin>>n;
    init();
    for(int i=1;i<=n;i++){
        int v;
        cin>>val[i]>>v;
        int ri=root(i),rv=root(v);
        if(ri==rv){
            cir.push_back(pir(i,v));
            continue;
        }else pre[rv]=ri;
        adj[i].push_back({v,i});
        adj[v].push_back({i,i});
    }
    ll ans=0;
    for(auto awa:cir){
        dfs(awa.first,0);
        ll ret=f[awa.first][0];
        dfs(awa.second,0);
        ans+=max(ret,f[awa.second][0]);
    }
    cout<<ans;
    return 0;
}

2.4 有向基环树最大独立集改编——洛谷P10933

一个显然的想法就是 $i\rightarrow A[i]$ 连边，但是发现是内向基环树有一点难做，我们不妨反过来连边，这样就变成了上面提到的有向基环树。

考虑转移方程，定义和最大独立集差不太多，但是方程有细微的变化。

f[u][0]=\sum\limits_{v\in son(u)}\max(f[v][0],f[v][1])

f[u][1]=1+\sum\limits_{v\in son(u)}f[v][0]+\sum\limits_{v' \in son(u),v'\neq v}\max(f[v'][0],f[v'][1])

第二个方程就是当前选了其他可以任意选择，因为题面说了只能限制一个。

但是 $O(n^2)$ 我们不喜欢可以改变以下：

f[u][1]=1+f[u][0]-\min\limits_{v\in son(u)} ( \max(f[v][0],f[v][1])-f[v][0] )

当然这个和2.3一样我们也需要考虑，但这里我们是忽略了 $u$ 可以限制 $v$ 的条件，我们可以强制限制计算。

#include<bits/stdc++.h>
using namespace std;
constexpr int MN=1e6+15;
int n,fa[MN],f[MN][2];
bool vis[MN];
vector<int> adj[MN];

int dodp(int u,int mode,int rt){
    f[u][0]=f[u][1]=0;
    vis[u]=1;
    int minp=1e9;
    for(auto v:adj[u]){
        if(v==rt) continue;
        int ret=dodp(v,mode,rt);
        minp=min(minp,ret-f[v][0]);
        f[u][0]+=ret;
    }
    f[u][1]=f[u][0]+1-(mode&&u==fa[rt]?0:minp);
    return max(f[u][0],f[u][1]);
}

int getlp(int u){
    vis[u]=1;
    if(vis[fa[u]]) return u;
    else return getlp(fa[u]);

}

int solve(int u){
    int lp=getlp(u);
    int ret1=dodp(lp,0,lp),ret2=dodp(lp,1,lp);
    return max(ret1,f[lp][0]);
}

int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>fa[i];
        adj[fa[i]].push_back(i);
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        if(!vis[i]) ans+=solve(i);
    }
    cout<<ans;
    return 0;
}