基环树
题目：骑士题目大意：
给出n个骑士，每个骑士有且仅有一个厌恶的骑士（用边相连），我们需要选出一些骑士，条件是，骑士团中不能存在他们讨厌的骑士。
思路：
将这种关系抽象成图：一个n个点，n个边的图（每个点有对应的一个边），图中存在环。考虑用基环树解题。
算法步骤：
1、对于每个点:1~n
2、若之前访问过这个点，不进行再次访问。
否则，以这个点为根进行深度优先搜索，找出一个环，并找出两个顶点，使得这两个顶点连接的边断开之后，
能形成以这两个顶点为根的两棵树。
3、对这两棵树进行树形dp，求出这两棵树的dp最大值。然后取max，值加入res
4、输出res，得到最终结果。关键：用st状态访问数组，判断每个点是否访问过，访问过的点不再访问，避免因为环造成死循环，同时避免同一个点的值多次相加
树形dp的过程参考：没有上司的舞会
#include using i64 = long long;const int N = 2e6 + 10;i64 n;std::vector g, w(N);std::vector dp(N);bool st;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) 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.first, dp.second); dp.second += dp.first; } return dp.first; // 返回dp，保证当前节点不选，这样才能保证环上两个节点不能同时被选，而不选这个点的话，最优情况就是对这两个端点的树形dp取最大值就行}void solve() { // register 用于将局部变量存储到寄存器中，提高访问速度 std::cin >> n; for (int i = 1; i > w >> v; g.push_back(i); } i64 res = 0; for (int i = 1; i
页:
[1]