给出n个点n条边和每个点的点权，一条边的两个断点不能同时选择，问最大可以选多少。
//图是一张基环外向树森林
是不是很像舞会啊～ 就是多了一条边。 所以我们考虑一下对于一棵基环外向树，拆掉一条在环上的边，变成一棵树。在这个树上以断边的一个断点为根，跑舞会，就得到了这棵树的最大值（根选和根不选了两种）。考虑到对于拆下来的内一条边，也要满足断点不能同时选择，所以此时得到的答案中，根不选一定是正确的，但是根选不一定是正确的（因为我们不知道此刻另一个断点是否被选择）。 那么我们强制该点不选，然后更新至根选的状态即可。#include#include #define N 1000010typedef long long ll;using namespace std;int n,a[N],f[N],head[N],ecnt=1,cnt[N];ll dp[N][2],ans;bool vis[N];struct hhh{ int to,next;}edge[N];int read(){ int ans=0,fu=1; char j=getchar(); for (;j<'0' || j>'9';j=getchar()) if (j=='-') fu=-1; for (;j>='0' && j<='9';j=getchar()) ans*=10,ans+=j-'0'; return ans*fu;}void add(int u,int v){ edge[ecnt].to=v; edge[ecnt].next=head[u]; head[u]=ecnt++;}void dfs(int x)//经典dp{ vis[x]=1; dp[x][1]=a[x]; for (int i=head[x];i;i=edge[i].next) if (!vis[edge[i].to]) { dfs(edge[i].to); dp[x][0]+=max(dp[edge[i].to][0],dp[edge[i].to][1]); dp[x][1]+=dp[edge[i].to][0]; }}void DP(int x){ int root; for (root=x;cnt[root]!=x;root=f[root]) cnt[root]=x; dfs(root); x=f[root];//x为当前根，那么不在树上的那条边就是x和f[x]的边，所以强制f[x]不选 dp[x][1]=dp[x][0]; for (x=f[x];x!=root;x=f[x]) { dp[x][0]=0;dp[x][1]=a[x]; for (int i=head[x];i;i=edge[i].next) { dp[x][0]+=max(dp[edge[i].to][0],dp[edge[i].to][1]); dp[x][1]+=dp[edge[i].to][0]; } } dp[root][1]=a[root]; for (int i=head[root];i;i=edge[i].next) dp[root][1]+=dp[edge[i].to][0];//强制根选，则+=儿子们都不选 ans+=max(dp[root][0],dp[root][1]);//取当前基环外向树的最大值}int main(){ n=read(); for (int i=1;i<=n;i++) a[i]=read(),f[i]=read(),add(f[i],i); for (int i=1;i<=n;i++)//基环外向树森林 if (!vis[i]) DP(i); printf("%lld\n",ans); return 0;}