1 #include2 #include 3 #define M 1000001 4 using namespace std; 5 int head[M],next[M],u[M],n,v[M],fa[M],cnt,q[M],f1[M],xia[M],ans; 6 long long dp[M][2],sum,f[M][4]; 7 void jia(int a1,int a2) 8 { 9 cnt++;10 next[cnt]=head[a1];11 head[a1]=cnt;12 u[cnt]=a2;13 return;14 }15 void tdp(int a1)16 {17 f1[a1]=1;18 dp[a1][0]=0;19 dp[a1][1]=v[a1];20 for(int i=head[a1];i;i=next[i])21 {22 tdp(u[i]);23 dp[a1][0]+=max(dp[u[i]][0],dp[u[i]][1]);24 dp[a1][1]+=dp[u[i]][0];25 }26 return;27 }28 int main()29 {30 scanf("%d",&n);31 for(int i=1;i<=n;i++)32 {33 int a1;34 scanf("%d%d",&v[i],&a1);35 jia(a1,i);36 fa[i]=a1;37 }38 for(int i=1;i<=n;i++)39 if(!f1[i])40 {41 q[0]=0;42 int k=i;43 for(;!f1[k];)44 {45 f1[k]=1;46 k=fa[k];47 xia[fa[k]]=k;48 }49 int now=k;50 for(;;)51 {52 dp[k][1]=v[k];53 for(int j=head[k];j;j=next[j])54 if(u[j]!=xia[k])55 {56 tdp(u[j]);57 dp[k][0]+=max(dp[u[j]][0],dp[u[j]][1]);58 dp[k][1]+=dp[u[j]][0]; 59 }60 q[0]++;61 q[q[0]]=k;62 k=fa[k];63 if(k==now)64 break;65 }66 f[1][0]=dp[q[1]][1];67 f[1][1]=0;68 f[1][2]=0;69 f[1][3]=dp[q[1]][0];70 for(int j=2;j<=q[0];j++)71 {72 f[j][0]=f[j-1][1]+dp[q[j]][1];73 f[j][1]=max(f[j-1][1],f[j-1][0])+dp[q[j]][0];74 f[j][2]=f[j-1][3]+dp[q[j]][1];75 f[j][3]=max(f[j-1][2],f[j-1][3])+dp[q[j]][0];76 }77 sum+=max(f[q[0]][1],max(f[q[0]][2],f[q[0]][3]));78 }79 printf("%lld",sum);80 return 0;81 }
如果把读入都建出边，这就是一个森林，每颗树可能有环，如果没有环的话，这就是一个简单的选儿子不能选爸爸的树形dp，由于n个点，n条边，所以最多是基环树森林，那就拆环，环上用
两个数组跑，保证拆开的边上的两个点一定不被同时选。