基环树

题目：骑士

题目大意：

给出n个骑士，每个骑士有且仅有一个厌恶的骑士（用边相连），我们需要选出一些骑士，条件是，骑士团中不能存在他们讨厌的骑士。
思路：

将这种关系抽象成图：一个n个点，n个边的图（每个点有对应的一个边），图中存在环。考虑用基环树解题。
算法步骤：

1. 1、对于每个点:1~n
2. 2、若之前访问过这个点，不进行再次访问。
3.    否则，以这个点为根进行深度优先搜索，找出一个环，并找出两个顶点，使得这两个顶点连接的边断开之后，
4.    能形成以这两个顶点为根的两棵树。
5. 3、对这两棵树进行树形dp，求出这两棵树的dp最大值。然后取max，值加入res
6. 4、输出res，得到最终结果。

复制代码

关键：用st状态访问数组，判断每个点是否访问过，访问过的点不再访问，避免因为环造成死循环，同时避免同一个点的值多次相加
树形dp的过程参考：没有上司的舞会
[code]#include using i64 = long long;const int N = 2e6 + 10;i64 n;std::vector g[N], w(N);std::vector dp(N);bool st[N];void find(int u, int root, int &r1, int &r2) {    st = true;    // 遍历每个儿子    for (auto e : g) {        if (e == root) {            r1 = u, r2 = e;            return;        }        if (st[e]) continue;        find(e, root, r1, r2);    }}i64 dfs(int u, int root) {    dp.first = 0, dp.second = w;    if (g.size() == 0) return 0;    for (auto e : g) {        if (e == root) continue; // 避免重复计算，保证当前的数据结构是一棵树        dfs(e, root);        dp.first += std::max(dp[e].first, dp[e].second);        dp.second += dp[e].first;    }    return dp.first; // 返回dp[0]，保证当前节点不选，这样才能保证环上两个节点不能同时被选，而不选这个点的话，最优情况就是对这两个端点的树形dp取最大值就行}void solve() {        // register 用于将局部变量存储到寄存器中，提高访问速度    std::cin >> n;    for (int i = 1; i > w >> v;        g[v].push_back(i);    }    i64 res = 0;    for (int i = 1; i