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;
}
