BZOJ_1040_[ZJOI2008]骑士_树形DP
题意：
Z国的骑士团是一个很有*的组织，帮会中汇聚了来自各地的精英。他们劫富济贫，惩恶扬善，受到社会各界的赞扬。最近发生了一件可怕的事情，邪恶的Y国发动了一场针对Z国的侵略战争。战火绵延五百里，在和平环境中安逸了数百年的Z国又怎能抵挡的住Y国的军队。于是人们把所有的希望都寄托在了骑士团的身上，就像期待有一个真龙天子的降生，带领正义打败邪恶。骑士团是肯定具有打败邪恶*的能力的，但是骑士们互相之间往往有一些矛盾。每个骑士都有且仅有一个自己最厌恶的骑士（当然不是他自己），他是绝对不会与自己最厌恶的人一同出征的。战火绵延，人民生灵涂炭，组织起一个骑士军团加入战斗刻不容缓！国王交给了你一个艰巨的任务，从所有的骑士中选出一个骑士军团，使得军团内没有矛盾的两人（不存在一个骑士与他最痛恨的人一同被选入骑士军团的情况），并且，使得这支骑士军团最具有战斗力。为了描述战斗力，我们将骑士按照1至N编号，给每名骑士一个战斗力的估计，一个军团的战斗力为所有骑士的战斗力总和。
分析：
可以发现图是由若干个连通块组成，每个连通块都是一个基环树。
我的做法是标记一下每个连通块有没有环。
如果有环则拆环，做两遍树形ＤＰ。
代码（丑）：
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define N 1000050
#define LL long long
int head[N],to[N<<1],nxt[N<<1],cnt,n;
int fa[N],root,son,rt[N],so[N],lian[N];
LL f[N],g[N],val[N];
inline void add(int u,int v){
to[++cnt]=v;nxt[cnt]=head[u];head[u]=cnt;
}
int find(int x){
return fa[x]==x?x:fa[x]=find(fa[x]);
}
void dfs3(int x,int y){
f[x]=val[x];
for(int i=head[x];i;i=nxt[i]){
if(to[i]!=y){
dfs3(to[i],x);
f[x]+=g[to[i]];
g[x]+=max(f[to[i]],g[to[i]]);
f[to[i]]=g[to[i]]=0;
}
}
}
void dfs1(int x,int y){
if(x!=son)f[x]=val[x];
for(int i=head[x];i;i=nxt[i]){
if(to[i]!=y){
dfs1(to[i],x);
if(x!=son)
f[x]+=g[to[i]];
if(to[i]==son)g[x]+=g[to[i]];
else g[x]+=max(f[to[i]],g[to[i]]);
f[to[i]]=g[to[i]]=0;
}
}
}
void dfs2(int x,int y){
if(x!=root)f[x]=val[x];
for(int i=head[x];i;i=nxt[i]){
if(to[i]!=y){
dfs2(to[i],x);
if(x!=root)
f[x]+=g[to[i]];
if(to[i]==root)g[x]+=g[to[i]];
else g[x]+=max(g[to[i]],f[to[i]]);
f[to[i]]=g[to[i]]=0;
}
}
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)fa[i]=i;
int x;
for(int i=1;i<=n;i++){
scanf("%lld%d",&val[i],&x);
int di=find(i),dx=find(x);
if(di!=dx){
fa[di]=dx;lian[dx]|=lian[di];
add(i,x);add(x,i);
}
else{
rt[di]=rt[dx]=i;
so[di]=so[dx]=x;
lian[di]=lian[dx]=1;
}
}
LL ans=0;
for(int i=1;i<=n;i++){
if(fa[i]==i){
if(!lian[i]){
dfs3(i,0);
ans+=max(f[i],g[i]);
}else{
root=rt[i],son=so[i];
dfs1(root,0);
LL now=max(f[root],g[root]);
f[root]=g[root]=0;
dfs2(son,0);
ans+=max(max(now,f[son]),g[son]);
}
}
}
printf("%lld\n",ans);
}