01、基环树

基环树是只有一个环的连通图，它有n个点和n条边。基环树不是一棵树，而是一棵“伪树”。它的特征是图中有且只有一个连通的环。下面分别讨论无向图和有向图两种情况下的基环树。

(1) 无向图上的基环树。在一棵基于无向图的无根树上加一条边，形成基环树。去掉环上任意一条边，基环树变成一棵真正的树。

(2) 有向图上的基环树。一个有向无环图(DAG)，如果在图中加一条边能形成一个自连通的环，则形成一棵基环树。把这个环看作一个整体，根据它与环外点的关系，把基环树分成两种：内向树，环外的点只能进入环内；

外向树，环外的点无法进入环内。

图1(1)~图1(3)是基环树的3种形态，把环缩成一个“虚点”后得到图1(4)~图1(6)。请注意，缩成虚点后的无向图1(4)是一棵树，但是缩成虚点后的有向图1(5)和图1(6)不一定是真正的树，如图1(5)就不是一棵树。

■ 图1 基环树的三种形态和缩点图

由基环树的特征可知，与基环树有关的题目，首先是找到唯一的环，然后把这个环当作“虚点”。

由前面的无向图的连通性和有向图的连通性可知，基环树的找环问题是“图的连通性”的一个简化问题。

对于无向图，用拓扑排序的BFS可以找出环，操作结束后，度大于1的点就是环上的点。具体做法：①计算所有点的度；②把所有度为1的点入队；③从队列弹出度为1的点，把它所连的边去掉，并将边所连的邻居点的度减1，若这个邻居的度变为1，入队；④继续执行步骤③直到队列为空。操作结束后，统计所有点，度数大于1的点即为环上的点。注意，这种无向图找环的方法只适用于只有一个环的基环树。

如果只要找环上的一个点，用DFS可以方便地找到。如果有一个点v第2次被访问到，那么就存在环，且v是环上的一个点。这个方法可用于有向图和无向图。下面的例题用到了这个原理。

把x讨厌的人y设为x的父节点，形成从y指向x的有向边。本题每个点的入度为1，生成的图中包括很多独立的连通块，每个连通块肯定是一棵基环树，而且形状是一棵外向树。这些基环树形成了基环树森林。在每棵基环树上找到环，断开这个环后，这棵基环树变成了一棵真正的树，就可以套用洛谷P1352的做法了。

本题属于“基环树+树上DP”，下面给出代码。其中的DP代码和洛谷P1352一样，这里不再解释。基环树部分有以下两处。

(1) 找基环树环上一个点。用check_c()函数实现，它是一个DFS，如果发现某个点被第2次访问，它就是环上的一个点，用mark记录这个点。

(2) 分别断开mark和mark的父节点，形成两棵树，在这两棵树上分别做DP，取最大值。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 100;
vector<int> G[N];
int father[N],val[N],mark;
bool vis[N];
ll dp[N][2];
void addedge(int from,int to){
    G[from].push_back(to);          //用邻接表建树
    father[to] = from;              //父子关系
}
void dfs(int u){                    //和洛谷P1352 几乎一样
    dp[u][0] = 0;                   //赋初值：不参加
    dp[u][1] = val[u];              //赋初值：参加
    vis[u] = true;
    for(int v : G[u]){              //遍历u的邻居v
        if(v == mark)  continue;   
        dfs(v);
        dp[u][1] += dp[v][0];       //父结点选择，子结点不选
        dp[u][0] += max(dp[v][0],dp[v][1]);  //父结点不选，子结点可选可不选
    }
}
int check_c(ll u){                  //在基环树中找环上一个点
    vis[u] = true;
    int f = father[u];
    if(vis[f]) return f;            //第2次访问到，是环上一个点
    else       check_c(f);          //继续向父结点方向找
}
ll solve(int u){                    //检查一棵基环树
    ll res = 0;
    mark = check_c(u);              //mark是基环树的环上一个点 
    dfs(mark);                      //做一次dfs
    res = max(res,dp[mark][0]);     //mark不参加
    mark = father[mark];
    dfs(mark);                      //mark的父结点不参加，再做一次dfs
    res = max(res,dp[mark][0]);
    return res;
}
int main(){
    int n; scanf("%d",&n);
    for(int i = 1;i <= n;i++){
        int d;   scanf("%d%d",&val[i],&d);    addedge(d,i);
    }
    ll ans = 0;
    for(int i = 1;i <= n;i++)
        if(!vis[i]) ans += solve(i);  //逐个检查每棵基环树
    printf("%lld\n",ans);
    return 0;
}