[ZJOI2008]骑士
Time Limit:10000MS Memory Limit:165536K
Total Submit:62 Accepted:30
Case Time Limit:2000MS
Description
Z国的骑士团是一个很有势力的组织，帮会中汇聚了来自各地的精英。他们劫富济贫，惩恶扬善，受到社会各界的赞扬。
最近发生了一件可怕的事情，邪恶的Y国发动了一场针对Z国的侵略战争。战火绵延五百里，在和平环境中安逸了数百年的Z国又怎能抵挡的住Y国的军 队。于是人们把所有的希望都寄托在了骑士团的身上，就像期待有一个真龙天子的降生，带领正义打败邪恶。
骑士团是肯定具有打败邪恶势力的能力的，但是骑士们互相之间往往有一些矛盾。每个骑士都有且仅有一个自己最厌恶的骑士（当然不是他自己），他是绝 对不会与自己最厌恶的人一同出征的。
战火绵延，人民生灵涂炭，组织起一个骑士军团加入战斗刻不容缓！国王交给了你一个艰巨的任务，从所有的骑士中选出一个骑士军团，使得军团内没有矛 盾的两人（不存在一个骑士与他最痛恨的人一同被选入骑士军团的情况），并且，使得这支骑士军团最具有战斗力。
为了描述战斗力，我们将骑士按照1至N编号，给每名骑士一个战斗力的估计，一个军团的战斗力为所有骑士的战斗力总和。
Input
第一行包含一个正整数N，描述骑士团的人数。
接下来N行，每行两个正整数，按顺序描述每一名骑士的战斗力和他最痛恨的骑士。
Output
应包含一行，包含一个整数，表示你所选出的骑士军团的战斗力。
Sample Input
3
10 2
20 3
30 1
Sample Output
30
【数据规模】
对于30%的测试数据，满足N ≤ 10；
对于60%的测试数据，满足N ≤ 100；
对于80%的测试数据，满足N ≤ 10 000。
对于100%的测试数据，满足N ≤ 1 000 000，每名骑士的战斗力都是不大于 1 000 000的正整数。
Source
啊啊啊。总算A掉了。。
61.187.179.132:8080/JudgeOnline/showproblem
注意到这样形成的图的每个联通块顶上必然是一堆树根组成的环，那么对每个树用树形DP算出选根和不选根的最大收入，然后就变成环上的问题了，就比较简单了。。
自己画的图，好悲剧囧。。
不过感觉我这个方法还不错，就是不是用树形DP去算，而是从底往上更新，每一种状态和规则都写一个类来表示更不容易出错(*^__^*) 。。
Code：
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
using namespace std;
const int inf=~0U>>1,maxn=1000000;
struct StateTree
{
long long A[2];
long long operator()(int v)const{return A[v];}
StateTree(int val=0)
{
A[0]=0;A[1]=val;
}
void Renew(const StateTree&son)
{
A[0]+=max(son(0),son(1));
A[1]+=son(0);
}
}Dp[maxn];
struct StateCircle
{
long long A[2][2];
long long operator()(int l,int r){return A[l][r];}
StateCircle(const StateTree&x)
{
memset(A,0,sizeof(A));
A[0][0]=x(0);
A[1][1]=x(1);
}
void Renew(const StateTree&x)
{
long long Ans[2][2];
rep(i,2)
{
Ans[i][0]=max(A[i][0],A[i][1])+x(0);
Ans[i][1]=A[i][0]+x(1);
}
memcpy(A,Ans,sizeof(A));
}
};
int In[maxn],P[maxn],C[maxn],n;
int main()
{
//freopen("in","r",stdin);
scanf("%d",&n);
rep(i,n) scanf("%d %d",C+i,P+i),In[–P[i]]++,Dp[i]=StateTree(C[i]);
queue<int> Q;
rep(i,n)if(!In[i]) Q.push(i);
while(Q.size())
{
int t=Q.front();Q.pop();
Dp[P[t]].Renew(Dp[t]);
if(–In[P[t]]==0) Q.push(P[t]);
}
long long Ans=0;
rep(i,n)if(In[i]>0)
{
In[i]=0;int t=i;
StateCircle now=StateCircle(Dp[t]);
t=P[t];
while(t!=i)
{
now.Renew(Dp[t]);In[t]=0;
t=P[t];
}
Ans+=max(now(1,0),max(now(0,0),now(0,1)));
}
cout<<Ans<<endl;
}