题目链接：
题意：给出一个图，只有一个环。每个点有一个权值。选出一些点两两不相邻，使得权值最大？
图中只有一个环，那么我们先建树，那么只有一条非树边，非树边上两个点我们设为node和root，那么我们DP两边，先让node不能选，然后让root不能选，DP两次即可，而且，环边不能走。
1 #include2 #include 3 #include 4 #include 5 #include 6 #define ll long long 7 int tot,go[2000005],next[2000005],first[1000005],b[2000005]; 8 int vis[1000005],root,tmp,node,flag,n; 9 ll f[1000005][2],w[1000005];10 void insert(int x,int y,int id){11 tot++;12 go[tot]=y;13 next[tot]=first[x];14 first[x]=tot;15 b[tot]=id;16 }17 void add(int x,int y,int id){18 insert(x,y,id);19 insert(y,x,id);20 }21 void dfs(int x,int fa){22 vis[x]=1;23 for (int i=first[x];i;i=next[i]){24 int pur=go[i];25 if (pur==fa) continue;26 if (vis[pur]){27 root=pur;28 node=x;29 tmp=b[i];30 continue;31 }32 dfs(pur,x);33 }34 }35 void dp(int x,int fa){36 f[x][0]=0;f[x][1]=0;37 for (int i=first[x];i;i=next[i]){38 int pur=go[i];39 if (b[i]==tmp||pur==fa) continue;40 dp(pur,x);41 f[x][0]+=std::max(f[pur][0],f[pur][1]);42 f[x][1]+=f[pur][0];43 }44 f[x][1]+=w[x];45 if (flag==0&&x==root) f[x][1]=0;46 if (flag==1&&x==node) f[x][1]=0;47 }48 int main(){49 scanf("%d",&n);50 int id=0;51 for (int i=1;i<=n;i++){52 int x;53 scanf("%lld%d",&w[i],&x);54 id++;55 add(i,x,id);56 }57 ll ans=0;58 ll Ans=0;59 for (int i=1;i<=n;i++)60 if (!vis[i]){61 node=tmp=0;62 dfs(i,0);63 flag=1;64 dp(root,0);65 Ans=std::max(f[root][0],f[root][1]);66 flag=0;67 dp(root,0);68 Ans=std::max(Ans,std::max(f[root][0],f[root][1]));69 ans+=Ans;70 }71 printf("%lld",ans);72 }