题解:
显然如果整张图没有环的话,就是一个无脑dp[u][0/1].
那么我们只需要考虑环上的一条边(u,v),分强制不选u和强制不选v两种情况,累计答案是取其中的较大值即可.1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #define MAXN 100001011 #define RG register12 #define LL long long int13 using namespace std;14 const int INF=1e9;15 const int mod=31011;16 struct node{17 int next;18 int to;19 }t[MAXN*2];20 int head[MAXN*2],num=1;21 int n;22 int L[MAXN],R[MAXN],B[MAXN],tot;23 LL dp[MAXN][2],val[MAXN],ans;24 int vis[MAXN*2];25 int fa[MAXN];26 void add(int from,int to)27 {28 t[++num].next=head[from];29 t[num].to=to;30 head[from]=num;31 }32 int find(int x)33 {34 if(fa[x]!=x) fa[x]=find(fa[x]);35 return fa[x];36 }37 void dfs(int u,int f)38 {39 dp[u][1]=val[u];dp[u][0]=0;40 for(int i=head[u];i;i=t[i].next)41 {42 int v=t[i].to;43 if(vis[i] || v==f) continue;44 dfs(v,u);45 dp[u][1]+=dp[v][0];46 dp[u][0]+=max(dp[v][0],dp[v][1]);47 }48 }49 int main()50 {51 freopen("1.in","r",stdin);52 scanf("%d",&n);53 for(int i=1;i<=n;i++) fa[i]=i;54 int x;55 for(int i=1;i<=n;i++){56 scanf("%lld%d",&val[i],&x);add(i,x);add(x,i);57 int f1=find(i),f2=find(x);58 if(f1!=f2) fa[f2]=f1;59 else { L[++tot]=i;R[tot]=x;B[tot]=num-1;}60 }61 for(int i=1;i<=tot;i++)62 {63 vis[B[i]]=vis[B[i]^1]=1;64 dfs(L[i],0);LL ans1=dp[L[i]][0];65 dfs(R[i],0);LL ans2=dp[R[i]][0];66 ans+=max(ans1,ans2);67 vis[B[i]]=vis[B[i]^1]=0;68 }69 printf("%lld\n",ans);70 return 0;71 }