Z国的骑士团是一个很有势力的组织，帮会中汇聚了来自各地的精英。他们劫富济贫，惩恶扬善，受到社会各界的赞扬。最近发生了一件可怕的事情，邪恶的Y国发动了一场针对Z国的侵略战争。战火绵延五百里，在和平环境中安逸了数百年的Z国又怎能抵挡的住Y国的军队。于是人们把所有的希望都寄托在了骑士团的身上，就像期待有一个真龙天子的降生，带领正义打败邪恶。骑士团是肯定具有打败邪恶势力的能力的，但是骑士们互相之间往往有一些矛盾。每个骑士都有且仅有一个自己最厌恶的骑士（当然不是他自己），他是绝对不会与自己最厌恶的人一同出征的。战火绵延，人民生灵涂炭，组织起一个骑士军团加入战斗刻不容缓！国王交给了你一个艰巨的任务，从所有的骑士中选出一个骑士军团，使得军团内没有矛盾的两人（不存在一个骑士与他最痛恨的人一同被选入骑士军团的情况），并且，使得这支骑士军团最具有战斗力。为了描述战斗力，我们将骑士按照1至N编号，给每名骑士一个战斗力的估计，一个军团的战斗力为所有骑士的战斗力总和。
第一行包含一个正整数N，描述骑士团的人数。接下来N行，每行两个正整数，按顺序描述每一名骑士的战斗力和他最痛恨的骑士。
应包含一行，包含一个整数，表示你所选出的骑士军团的战斗力。
对于100%的测试数据，满足N ≤ 1 000 000，每名骑士的战斗力都是不大于 1 000 000的正整数。
1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #define ll long long 5 using namespace std; 6 const int N=1000100; 7 int q[N],du[N],v[N],c[N],deep[N],fa[N],head[N],sz[N]; 8 int root,other,cnt,n,tot; 9 ll ans,end,tr[N][2]; 10 bool vis[N],pd[N],viss[N]; 11 struct ee{int to,next;}e[N*2]; 12 void ins(int u,int v){ 13 e[++cnt].next=head[u],e[cnt].to=v,head[u]=cnt;du[u]++; 14 e[++cnt].next=head[v],e[cnt].to=u,head[v]=cnt;du[v]++; 15 } 16 void topsort(){ 17 int l,r;l=r=0; 18 for (int i=1;i<=n;i++) if(du[i]==1) q[++r]=i,vis[i]=1; 19 while(l<r){ 20 int now=q[++l]; 21 for(int i=head[now];i;i=e[i].next){ 22 int v=e[i].to; 23 if(du[v]>1){ 24 du[v]--; 25 if(du[v]==1) q[++r]=v,vis[v]=1; 26 } 27 } 28 } 29 } 30 31 void dfs(int x,int t){ 32 vis[x]=t;c[x]=t; 33 for (int i=head[x];i;i=e[i].next){ 34 int v=e[i].to; 35 if(!vis[v]) dfs(v,t); 36 } 37 } 38 39 40 ll treedp(int x,int bz,int t){ 41 if(tr[x][bz]!=-1) return tr[x][bz]; 42 ll mid=0;bool flag=0;viss[x]=1; 43 for(int i=head[x];i;i=e[i].next){ 44 int vv=e[i].to; 45 if(deep[vv]==deep[x]+1) { 46 flag=1; 47 if(bz==0)mid+=max(treedp(vv,bz^1,t),treedp(vv,bz,t)); 48 else mid=mid+treedp(vv,bz^1,t); 49 } 50 } 51 if(bz==1) mid+=v[x]; 52 if(!flag)tr[x][bz]=bz*v[x];else tr[x][bz]=mid; 53 return tr[x][bz]; 54 } 55 56 void solve(int x,int bz,int t){ 57 vis[x]=1; 58 for (int i=head[x];i;i=e[i].next){ 59 int v=e[i].to; 60 if(x==root&&v==other) continue; 61 if(!vis[v]) deep[v]=deep[x]+1,solve(v,bz,t); 62 } 63 } 64 65 int main(){ 66 scanf("%d",&n);int x; 67 for(int i=1;i<=n;i++){ 68 scanf("%d%d",&v[i],&x); 69 sz[i]=x; 70 71 if (sz[x]!=i) ins(i,x); 72 fa[x]=i; 73 } 74 topsort(); 75 for(int i=1;i<=n;i++)if(!vis[i]) dfs(i,++tot); 76 memset(tr,-1,sizeof(tr)); 77 for (int i=1;i<=n;i++){ 78 if(c[i]&&!pd[c[i]]) { 79 other=0;root=i;deep[root]=0;pd[c[i]]=1; 80 for(int j=head[i];j;j=e[j].next){ 81 if(c[e[j].to]==c[i]) { 82 other=e[j].to; 83 break; 84 } 85 }ans=0; 86 memset(vis,0,sizeof(vis));vis[root]=1; 87 solve(root,0,c[i]); 88 ans=max(ans,treedp(root,0,c[i])); 89 root=other;deep[root]=0; 90 other=i; 91 memset(vis,0,sizeof(vis));vis[root]=1; 92 memset(tr,-1,sizeof(tr)); 93 solve(root,0,c[i]); 94 ans=max(ans,treedp(root,0,c[i])); 95 end+=ans; 96 } 97 } 98 other=-1; 99 memset(vis,0,sizeof(vis)); 100 for(int i=1;i<=n;i++) if(!viss[i]) { 101 root=i;solve(root,0,c[i]); 102 end+=max(treedp(root,0,0),treedp(root,1,0));} 103 printf("%lld",end); 104 }
原文：http://www.cnblogs.com/wuminyan/p/5202596.html