题目大意
从 \(n\) 个骑士中选择一个军团，使得：
- 不存在一个骑士与他最痛恨的骑士一同被选入。
- 所有选中骑士的战斗力总和最大。
关键：每个骑士都有且仅有一个自己痛恨的骑士（不是自己）。
分析
这些骑士之间的关系看起来类似于没有上司的舞会那道题，于是考虑直接进行树形DP，随机把一个点作为根节点进行 dfs，然后就 TLE 了，为什么呢？
如图：
这根本就不是树形结构嘛！
怎么办呢？难道我英明一世，如今就要败给这区区蓝题了吗？
于是你很快就想到了，直接在环上某一处把这个环断开不就可以当作树了吗！
然后你又犹豫了，如果一个连通块里面有很多个环咋办？要是只有一个环就好了。
关键：一个连通块里面真的只有一个环。
又如图：
此时这个图还不完整，因为 \(5\) 号点还少了一条出边，由于 \(5\) 号点只能指向 \(1\)\(-\)\(4\) 号点的其中一个，必定形成一个环。
于是你开开心心地先随机以一个点为根节点用 dfs 找出来环上的一条边，再分别把这条边的两个端点作为根节点进行 dfs ，然后你就会发现， WA 了，这又是为什么呢？
还是如图：
你只搜索了其中一个连通块，当然不对啦。
至此，这道题的坑基本就已经踩完了，这就是传说中的基环树森林。
基环树是一种有且只含有一个环的图，断开形成环的这条边之后就是树。
Solution
标签：基环树
步骤
- 找到环上的一条边。
- 删除这条边，将基环树变成树。
- 在树上进行树形 DP ，但要考虑被删除边的限制。
- 由于环上相邻两点不能同时选，需要强制其中一个不选，做两次 DP 取最大值。
- 对每个基环树的 DP 值进行累加即可。
时间复杂度
\(O(n)\)
参考代码
注意：题目描述是有向边，但为了找环方便，且没有其他影响，代码中使用的是无向边。
#include <bits/stdc++.h>
using namespace std;
#define N 2000010
typedef long long ll;int n; // 骑士数量
int cnt = 1; // 边计数器，从2开始（方便取反）
int to[N], head[N >> 1], nxt[N];
int vis[N >> 1]; // 访问标记
int lef, righ, idx; // 环上删除边的两个端点和边的编号
ll dp[N][2]; // dp[u][0]: 不选u的最大值，dp[u][1]: 选u的最大值
ll a[N >> 1]; // 每个骑士的战斗力
ll ans; void dfs(int u, int f) {dp[u][0] = 0; // 不选u，初始为0dp[u][1] = a[u]; // 选u，初始为u的战斗力// 遍历所有邻接点for (int i = head[u]; i; i = nxt[i]) {int v = to[i];if (v == f) continue; if (i == idx || i == (idx ^ 1)) continue; // 跳过被删除的边dfs(v, u); // 状态转移dp[u][0] += max(dp[v][1], dp[v][0]); // 不选u，v可选可不选dp[u][1] += dp[v][0]; // 选u，v必须不选}
}// 找环：在基环树中找到一个环
void find_circle(int u, int f) {vis[u] = 1; // 标记已访问for (int i = head[u]; i; i = nxt[i]) {int v = to[i];if (v == f) continue; // 跳过父节点if (vis[v]) { // 找到环了lef = u; // 环上一点righ = v; // 环上另一点idx = i; // 环上的边continue;}find_circle(v, u); // 继续搜索}
}int main() {cin >> n;// 建图for (int i = 1; i <= n; i++) {cin >> a[i]; // 骑士i的战斗力int f; // 骑士i讨厌的骑士cin >> f;to[++cnt] = i;nxt[cnt] = head[f];head[f] = cnt;to[++cnt] = f;nxt[cnt] = head[i];head[i] = cnt;}// 处理每个连通分量（基环树）for (int i = 1; i <= n; i++) {if (!vis[i]) {// 1. 找环find_circle(i, 0);// 2. 断环，做两次树形DP// 第一次：强制lef不选dfs(lef, 0);ll temp = dp[lef][0]; // 记录lef不选的结果// 第二次：强制righ不选dfs(righ, 0);// 3. 取两次的最大值，加到答案中ans += max(temp, dp[righ][0]);}}cout << ans;return 0;
}