题目链接：
https://www.lydsy.com/JudgeOnline/problem.php?id=1040
题目大意：
Z国的骑士团是一个很有势力的组织，帮会中汇聚了来自各地的精英。他们劫富济贫，惩恶扬善，受到社会各界的赞扬。最近发生了一件可怕的事情，邪恶的Y国发动了一场针对Z国的侵略战争。战火绵延五百里，在和平环境中安逸了数百年的Z国又怎能抵挡的住Y国的军队。于是人们把所有的希望都寄托在了骑士团的身上，就像期待有一个真龙天子的降生，带领正义打败邪恶。骑士团是肯定具有打败邪恶势力的能力的，但是骑士们互相之间往往有一 些矛盾。每个骑士都有且仅有一个自己最厌恶的骑士（当然不是他自己），他是绝对不会与自己最厌恶的人一同出征的。战火绵延，人民生灵涂炭，组织起一个骑士军团加入战斗刻不容缓！国王交给了你一个艰巨的任务，从所有的骑士中选出一个骑士军团，使得军团内没有矛盾的两人（不存在一个骑士与他最痛恨的人一同被选入骑士军团的情况），并且，使得这支骑士军团最具有战斗力。为了描述战斗力，我们将骑士按照1至N编号，给每名骑士一个战 斗力的估计，一个军团的战斗力为所有骑士的战斗力总和。
思路：
基环树：
求基环树森林的最大权独立集。
分解成多个基环树求解即可，对于每个基环树，只有一个环，任意去掉环上的一条边u，v，以u为根节点跑一遍DP，记录u不取的ans1，再以v为根节点跑一遍DP，记录v不取的ans2，这个基环树的最大权独立集就是max(ans1, ans2)
找出环上的一条边可以用并查集来做。
1 #include<bits/stdc++.h> 2 #define IOS ios::sync_with_stdio(false);//不可再使用scanf printf 3 #define Max(a, b) ((a) > (b) ? (a) : (b))//禁用于函数，会超时 4 #define Min(a, b) ((a) < (b) ? (a) : (b)) 5 #define Mem(a) memset(a, 0, sizeof(a)) 6 #define Dis(x, y, x1, y1) ((x - x1) * (x - x1) + (y - y1) * (y - y1)) 7 #define MID(l, r) ((l) + ((r) - (l)) / 2) 8 #define lson ((o)<<1) 9 #define rson ((o)<<1|1) 10 #define Accepted 0 11 #pragma comment(linker, "/STACK:102400000,102400000")//栈外挂 12 using namespace std; 13 inline int read() 14 { 15 int x=0,f=1;char ch=getchar(); 16 while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();} 17 while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} 18 return x*f; 19 } 20 21 typedef long long ll; 22 const int maxn = 1000000 + 10; 23 const int MOD = 1000000007;//const引用更快，宏定义也更快 24 const int INF = 1e9 + 7; 25 const double eps = 1e-6; 26 27 ll dp[maxn][2]; 28 ll a[maxn]; 29 int p[maxn]; 30 vector<int>G[maxn]; 31 32 int Find(int x) 33 { 34 return x == p[x] ? x : p[x] = Find(p[x]); 35 } 36 void dfs(int u, int fa) 37 { 38 dp[u][0] = 0; 39 dp[u][1] = a[u]; 40 for(int i = 0; i < G[u].size(); i++) 41 { 42 int v = G[u][i]; 43 if(v == fa)continue; 44 dfs(v, u); 45 dp[u][0] += max(dp[v][0], dp[v][1]); 46 dp[u][1] += dp[v][0]; 47 } 48 //cout<<u<<" "<<dp[u][0]<<" "<<dp[u][1]<<endl; 49 } 50 int u[maxn], v[maxn]; 51 int main() 52 { 53 int n, tot = 0; 54 scanf("%d", &n); 55 for(int i = 1; i <= n; i++)p[i] = i; 56 for(int i = 1; i <= n; i++) 57 { 58 int x; 59 scanf("%lld%d", &a[i], &x); 60 int a = Find(i), b = Find(x); 61 if(a == b)//基环树的环上的一条边 断开 62 { 63 u[tot] = i; //是基环树森林 有多个基环树 64 v[tot++] = x; 65 } 66 else 67 { 68 p[a] = b; 69 G[i].push_back(x); 70 G[x].push_back(i); 71 } 72 } 73 ll ans = 0, tmp; 74 for(int i = 0; i < tot; i++) 75 { 76 dfs(u[i], -1); 77 tmp = dp[u[i]][0];//不选u的最大值 78 dfs(v[i], -1); 79 tmp = max(tmp, dp[v[i]][0]);//不选v的最大值 80 ans += tmp; 81 } 82 printf("%lld ", ans); 83 return Accepted; 84 }