这是个基环数(森林) DP
题面
首先读完题，我们思考一下他都有什么性质：
1.乍一看有点像树形背包，因为他在选择物品的时候有依赖性，即选择某件物品之后，与之对应的某件物品无法使用
3.显然，一般一道题目没有明显说明“无环”的情况，肯定会有环的各种各样数据产生。
4.我认为也是最重要的，做题的话要尽可能地思索能得到什么，或者说你能想到解决问题的过程当中有什么困难，显然这个题"环”的处理不太好像。我们在建树的过程中是将自己厌恶的骑士当成自己的父亲（绝了），那么像构成环的话，每个点的出度都给了自己的父亲，那怎么才能出现环呢？谁的出度不会给父亲，只有根节点，所以一棵基环数有且仅有一个简单环且根节点必定在换之内。
然后我们可以开始想如何DP，显然，思考进行当前这一步选择的时候什么会影响到我，我会影响到什么，我选了，有的人就不能选，有的人选了，我就不能选，很明显的我“选不选”实在转移时必须要知道的条件，即状态f[i][1/0]表示以i为子树,当前i选/不选的最大值。
方程也很简单，模板
f[i][0] +=max(f[son][0],f[son][1]);
f[i][1] +=f[son][0] //不加当前的价值因为习惯性赋值f[now][1] = val[now]
其实说白了这道题就是没有上司的舞会 + 环的处理
怎么树形Dp呢，在找到一个环之后就把他拆成一棵树，随便删一条边即可，删的那条边的两个点就可以进行DP，然后肯定不能真正的修改图，可以强制选择其中一个点，做一次，在强制选择另一个点做一次。
剩下统计一下答案就输出了，思路非常清晰。
DP : think twice, code once
代码：
#include <bits/stdc++.h> using namespace std; const int N = 1e6 + 5; typedef long long LL; //DP 之前先明确：自己的任务有哪些 //1.找到每一棵基环数的环,随意的拆开 //2.做两遍树形Dp求Max. //小点:判断当前这是棵树，和森林区分开. //对于每一个节点，都需要看看根据他为根节点是不是一棵基环树,不是其实最好 int head[N], cnt; int n, val[N], inb; LL ans, f[N][2]; int fa[N], v; int fe, fw, fc, fv;//任意挑的两个和判断是否是基环数 bool vis[N]; struct Edge{ int to; int nxt; }e[N << 1]; void add(int x,int y){ e[++cnt] = (Edge){y, head[x]}, head[x] = cnt; } void dfs(int x, int fath){ vis[x] = true; for(int i = head[x];i;i = e[i].nxt){ v = e[i].to; if(v == fath) continue; if(!vis[v]) dfs(v, x); else if(vis[v] && !fv) fv = true, fc = i, fe = x, fw = v; } } void dp(int u, int fa) { f[u][0] = 0, f[u][1] = val[u]; for (int i = head[u], v; i; i = e[i].nxt) if ((v = e[i].to) != fa && i != fc && i != (fc ^ 1)) { dp(v, u); f[u][0] += max(f[v][0], f[v][1]); f[u][1] += f[v][0]; } } int main(){ cnt = 1; scanf("%d", &n); for(int i = 1;i <= n;++ i){ scanf("%d %d", &val[i], &inb); add(i, inb);//正常建边 add(inb, i); } for(int i = 1;i <= n;++ i){//每个点扫一遍 if(!vis[i]){ fv = false, fc = fe = fw = 0; dfs(i, 0); if(fv) {//有环 dp(fw, 0); LL tmp = f[fw][0]; dp(fe, 0); tmp = max(tmp, f[fe][0]); ans += tmp; } else { dp(i, 0); ans += max(f[i][0], f[i][1]); } } } printf("%lld", ans); return 0; }