题意: 给你一个基环树森林, 每个点有一个权值, 一条边上的两个节点不能同时选择. 选取任意个节点, 求最大权值和
对于每颗基环树: 找环→断边→树形 dp(没有上司的舞会)
- #include<iostream>
- #include<cstdio>
- #include<cstdlib>
- #include<cstring>
- #include<algorithm>
- #include<cmath>
- #define MAXN 1000005
- #define LL long long
- using namespace std;
- inline int read()
- {
- int f=1,x=0;
- char ch=getchar();
- while(ch<'0' || ch>'9') {if(ch=='-') f=-1; ch=getchar();}
- while(ch>='0' && ch<='9') {x=x*10+ch-'0'; ch=getchar();}
- return x*f;
- }
- int n,cnt=-1;
- int val[MAXN];
- int v[MAXN<<1],head[MAXN],nxt[MAXN<<1];
- int k1,k2,e;
- bool book[MAXN];
- LL f[MAXN][2],nans,ans;
- void add(int x,int y)
- {
- v[++cnt]=y;
- nxt[cnt]=head[x];
- head[x]=cnt;
- }
- void find_circle(int x,int fa)
- {
- book[x]=1;
- for(int i=head[x];i!=-1;i=nxt[i])
- {
- int t=v[i];
- if(t==fa) continue;
- if(book[t])
- {
- k1=x;
- k2=t;
- e=i;
- continue;
- }
- find_circle(t,x);
- }
- }
- void dfs(int x,int fa)
- {
- f[x][1]=val[x];
- f[x][0]=0;
- for(int i=head[x];i!=-1;i=nxt[i])
- {
- int t=v[i];
- if(i==e || (i^1)==e) continue;
- if(t==fa) continue;
- dfs(t,x);
- f[x][0]+=max(f[t][0],f[t][1]);
- f[x][1]+=f[t][0];
- }
- }
- int main()
- {
- memset(head,-1,sizeof(head));
- int i;
- int x;
- n=read();
- for(i=1;i<=n;i++)
- {
- val[i]=read();
- x=read();
- add(i,x);
- add(x,i);
- }
- for(i=1;i<=n;i++)
- {
- if(!book[i])
- {
- find_circle(i,-1);
- dfs(k1,-1);
- nans=f[k1][0];
- dfs(k2,-1);
- nans=max(nans,f[k2][0]);
- ans+=nans;
- }
- }
- printf("%lld",ans);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2876693.html