P2607
基环树板子题（虽然打了好久好久）
题目大意是给你一n个人的能力值，在每个人都有一个死敌不能同时被选中的情况下，从中挑出一些人，问能力值最大是多少。
首先，为什么会往基环树的方向思考呢？
- 两两死对头关系可以当作二人之间连一条边
- 如此一来，就有n条边
- n个点n条边，显然构成基环树
有了大致方向，再来思考一下具体实现。
首先要明确，基环树的构造是形如这样的：
（就是一个环，每个节点都延伸出一棵子树）
由于我们给死对头连边，问题就转换为了求有间隔地选出最大权值。
那么，我们可以先考虑每一个环上节点延伸的子树。十分显然，在每棵子树上“有间隔地选出最大权值”就是那道经典题目——没有上司的舞会。
好的，现在处理完了每一棵子树，考虑整个环的情况。本来以为到这里就结束了呢，可事情没那么简单。
对于整个环也是一样，我们要“有间隔地选出最大权值”。经试验，贪心是不行的。必须要进行动归。
在环做dp显然是不现实的（后效性），考虑破环为链。假定一个开始点，注意到它的选与不选只会影响到下一个以及上一个点，而且说是会影响第二个点，实际上也没有改变递推式！
所以我们只用分类讨论第一个点选或不选，然后暴力定最后一个点的状态即可。
好的，讲了这么久有的没的，发现漏讲怎么找环了。
这个题的特殊性导致了每个节点的出度只能为1。
所以对于每一个环上节点对应的子树，它的形态必定是这样的：
环内又必定是这样的：
所以不难发现，即使我们现在访问的是随意一个节点，我们最后也会绕到环里边。如果一个点被经过了2次就说明它一定在环上（一次从子树出来，一次绕着环回来）
接着，我们又利用环的形态性质就可以简单地 for (int i = f[st]; i != st; i = f[i]) 访问
代码如下qaq
#include <cstdio>
#include <vector>
#include <iostream>
using namespace std;
#define int long long
const int maxn = 1e6+100;
const int INF = 0x3f3f3f3f3f3f3f3f;
int n,w[maxn],f[maxn],st,ans;
bool vis[maxn], circle[maxn];
int dp[maxn][2], cur[5], chose[maxn][2];
vector<int> adj[maxn];
void find(int u) {
// cout << u << endl;
if (vis[u]) {
st = u;
return;
}
vis[u] = true;
find(f[u]);
}
void dfs(int u, int fa) {
vis[u] = 1;
dp[u][0] = 0, dp[u][1] = w[u];
for (auto v:adj[u]) {
if (v != fa && !circle[v]) {
// cout << "shit" << endl;
dfs(v,u);
dp[u][0] += max(dp[v][0], dp[v][1]);
dp[u][1] += dp[v][0];
}
}
}
void DP() {
circle[st] = 1;
for (int i = f[st]; i != st; i = f[i]) vis[i] = 1, circle[i] = 1;
int u = st, cnt = 0;
while (true) {
if (cnt && u == st) break;
cnt = 1;
dfs(u,0);
// printf("dp[%d][0] = %d; dp[%d][1] = %d\n",u,dp[u][0],u,dp[u][1]);
u = f[u];
}
}
void choose() {
int res;
//choose first one
chose[st][0] = -INF, chose[st][1] = dp[st][1];
int lst = st;
for (int i = f[st]; i != st; i = f[i]) {
chose[i][0] = max(chose[lst][1],chose[lst][0]) + dp[i][0];
chose[i][1] = (chose[lst][0] == -INF)?-INF :chose[lst][0]+dp[i][1];
lst = i;
}
res = chose[lst][0];
//don't choose 1st
chose[st][1] = -INF, chose[st][0] = dp[st][0];
lst = st;
for (int i = f[st]; i != st; i = f[i]) {
chose[i][0] = max(chose[lst][1],chose[lst][0]) + dp[i][0];
chose[i][1] = chose[lst][0]+dp[i][1];
lst = i;
}
ans += max(max(chose[lst][1],chose[lst][0]),res);
}
signed main() {
// freopen("2.in","r",stdin);
scanf("%lld",&n);
for (int i = 1; i <= n; i++) {
scanf("%lld%lld",&w[i],&f[i]);
//son tree dp
adj[i].push_back(f[i]), adj[f[i]].push_back(i);
}
for (int i = 1; i <= n; i++) {
if (!vis[i]) {
find(i);
// cout << st << endl;
DP();
choose();
}
}
printf("%lld\n", ans);
return 0;
}
/*
10
30 2
20 3
20 1
15 1
25 1
22 5
14 2
26 7
24 3
30 3
*/