题目大意

有 $n$ 个骑士，每人有一个战斗力 $v_i$，并且有且仅有一个厌恶的骑士 $h_i$（不能和自己一起出征）。
要选出若干骑士，使得集合中任意两人不互相厌恶，并且战斗力总和最大。

问题分析

1. 图的模型

• 将每个骑士看作一个结点。
• 从每个骑士向他厌恶的骑士连一条有向边（或者无向边，因为关系是相互排斥的）。
• 由于每个点恰有一条出边，整个图由若干棵 基环树（每个连通分量恰好有一个环）组成。

2. 基环树结构

基环树的特点是：去掉环上的一条边后，剩余部分变成若干棵树。
本题中，环表示一群骑士形成一个“矛盾循环”。

3. 问题转化

我们需要在基环树森林中求 最大权独立集（选出的结点不相邻）。
对于树上的最大权独立集，可以用树形 DP 解决：

• 设 $dp[u][0]$ 表示不选结点 $u$ 时，以 $u$ 为根的子树的最大权和；
• 设 $dp[u][1]$ 表示选结点 $u$ 时，以 $u$ 为根的子树的最大权和。
• 转移：
  • 不选 $u$，则子结点可选可不选：$dp[u][0] = \sum \max(dp[v][0], dp[v][1])$
  • 选 $u$，则子结点不可选：$dp[u][1] = val[u] + \sum dp[v][0]$

4. 环上的处理

对于基环树，我们可以：

1. 找到环上的一条边 $E$（连接 $u$ 和 $v$）。
2. 断开这条边，将基环树变成一棵树。
3. 分别强制 不选 $u$ 和 不选 $v$，做两次树形 DP（因为 $u$ 和 $v$ 在环上相邻，不能同时选）。
4. 取两次结果的最大值作为这个连通分量的答案。

5. 算法步骤

• 用 DFS 或拓扑排序（入度判断）找出所有环。
• 对每个连通分量（基环树）：
  1. 找环并标记一条边 $E(u \to v)$。
  2. 以 $u$ 为根，强制不选 $u$，做树形 DP，得到 $ans_1$。
  3. 以 $v$ 为根，强制不选 $v$，做树形 DP，得到 $ans_2$。
  4. 此分量的最大独立集权值为 $\max(ans_1, ans_2)$。
• 将所有连通分量的答案相加。

复杂度

• 每个结点访问 $O(1)$ 次，总复杂度 $O(n)$。
• 满足 $n \le 10^6$ 的要求。

关键点

• 将问题转化为基环树森林的最大权独立集。
• 通过 断环 + 两次树形 DP 处理环的限制。
• 注意关系是相互的，建无向图，但找环时需小心。