题目大意：有一些骑士，他们每个人都有一个权值。但是由于一些问题，每一个骑士都特别讨厌另一个骑士。所以不能把他们安排在一起。求这些骑士所组成的编队的最大权值和是多少。

思路：首先貌似是有向图的样子，但是一个人讨厌另一个人，他们两个就不能在一起，所以边可以看成是无向的。

n个点，n条无向边，好像是一颗基环树。但其实这是一个基环树林，因为题中并没有说保证图一定联通。

然后就可以深搜了，处理出每一个联通块。其实每一个联通块就是一个基环树，在这个基环树上进行树形DP。求出最大值，然后累加到答案上。答案要开long long。

树形DP具体的过程是，去掉一条边，使这个基环树变成一颗树，然后进行正常的树形DP。在环上任找一点，和与之相邻的一点，标记他们之间的边，在一会dp的时候不能经过这条边，然后从选择的第一个点dp。f[i]表示取这个点的时候最大的权值和，g[i]表示不取这个点的时候的最大权值和。

进行完dp后，取刚才选取的树的根的g的值g[root]来更新答案。然后再对与它相邻的点进行dp，用g[_root]来更新答案。

CODE：

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #define MAX 1000010 using namespace std; int points; int src[MAX]; int head[MAX],total = 1; int next[MAX << 1],aim[MAX << 1]; long long f[MAX],g[MAX],ans; int root,_root; bool v[MAX],found; int not_pass; inline void Add(int x,int y); void DFS(int x,int last); void TreeDP(int x,int last); int main() { cin >> points; for(int x,i = 1;i <= points; ++i) { scanf("%d%d",&src[i],&x); Add(i,x),Add(x,i); } for(int i = 1;i <= points; ++i) if(!v[i]) { DFS(i,-1); TreeDP(root,-1); long long temp = g[root]; TreeDP(_root,-1); temp = max(temp,g[_root]); ans += temp; } cout << ans << endl; return 0; } inline void Add(int x,int y) { next[++total] = head[x]; aim[total] = y; head[x] = total; } void DFS(int x,int last) { v[x] = true; for(int i = head[x];i;i = next[i]) { if(aim[i] == last) continue; if(!v[aim[i]]) DFS(aim[i],x); else { not_pass = i; root = aim[i]; _root = x; } } } void TreeDP(int x,int last) { f[x] = src[x],g[x] = 0; for(int i = head[x];i;i = next[i]) { if(aim[i] == last) continue; if(i == not_pass || i == (not_pass^1)) continue; TreeDP(aim[i],x); f[x] += g[aim[i]]; g[x] += max(f[aim[i]],g[aim[i]]); } }