题目描述 Description
Z国的骑士团是一个很有*的组织，帮会中汇聚了来自各地的精英。他们劫富济贫，惩恶扬善，受到社会各界的赞扬。
最近发生了一件可怕的事情，邪恶的Y国发动了一场针对Z国的侵略战争。战火绵延五百里，在和平环境中安逸了数百年的Z国又怎能抵挡的住Y国的军队。于是人们把所有的希望都寄托在了骑士团的身上，就像期待有一个真龙天子的降生，带领正义打败邪恶。
骑士团是肯定具有打败邪恶*的能力的，但是骑士们互相之间往往有一些矛盾。每个骑士都有且仅有一个自己最厌恶的骑士（当然不是他自己），他是绝对不会与自己最厌恶的人一同出征的。
战火绵延，人民生灵涂炭，组织起一个骑士军团加入战斗刻不容缓！国王交给了你一个艰巨的任务，从所有的骑士中选出一个骑士军团，使得军团内没有矛盾的两人（不存在一个骑士与他最痛恨的人一同被选入骑士军团的情况），并且，使得这支骑士军团最具有战斗力。
为了描述战斗力，我们将骑士按照1至N编号，给每名骑士一个战斗力的估计，一个军团的战斗力为所有骑士的战斗力总和。
输入描述 Input Description
第一行包含一个正整数N，描述骑士团的人数。
接下来N行，每行两个正整数，按顺序描述每一名骑士的战斗力和他最痛恨的骑士。
输出描述 Output Description
应包含一行，包含一个整数，表示你所选出的骑士军团的战斗力。
样例输入 Sample Input
样例输出 Sample Output
数据范围及提示 Data Size & Hint
对于30%的测试数据，满足N ≤ 10；
对于60%的测试数据，满足N ≤ 100；
对于80%的测试数据，满足N ≤ 10 000。
对于100%的测试数据，满足N ≤ 1 000 000，每名骑士的战斗力都是不大于 1 000 000的正整数。
这道题很容易就可以想到树形dp，但是会出现环，就先把树上进行树形动规，然后再在
环上进行dp，环上的dp就从一个地方切开，然后增加一个状态，选第一个点和不选第一个点
关于树形dp还是再说两句，用f[i]表示i骑士选的最大战斗力（仅限这棵子树），g[i]表示不选
i骑士
得到了方程:
f[i] = sum{g[son[i][j]]};
g[i] = sum{max(g[son[i][j]], f[son[i][j]])};
（注:son[i][j]表示i节点的第j个子节点的编号，实际编程中可直接用存图的方式来储存）
Code
/**
* codevs.cn
* Problem#1423
* Accepted
* Time:1478ms
* Memory:58768k
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<stack>
#include<vector>
using namespace std;
typedef bool boolean;
template<typename T>
void readInteger(T& u){
char x;
while(!isdigit((x = getchar())));
for(u = x - ''; isdigit((x = getchar())); u = (u << ) + (u << ) + x - '');
ungetc(x, stdin);
}
typedef class Edge{
public:
int end;
int next;
Edge(const int end = , const int next = ):end(end),next(next){}
}Edge;
int ce;
int *h;
Edge* edge;
inline void addEdge(int from, int end){
edge[++ce] = Edge(end, h[from]);
h[from] = ce;
}
int cc;
int *visitID;
int *exitID;
boolean *visited;
boolean *inStack;
int entryed;
stack<int> sta;
vector<int> *start;
void getSonMap(int end){
vector<int> buf;
int now = -;
int exits = ;
while(now != end){
now = sta.top();
inStack[now] = false;
exits++;
buf.push_back(now);
sta.pop();
}
if(exits > ){
for(int i = ; i < exits; i++){
start[cc].push_back(buf[i]);
}
cc++;
}
}
void Tarjan(const int pi){
int index = h[pi];
visitID[pi] = ++entryed;
exitID[pi] = visitID[pi];
visited[pi] = true;
inStack[pi] = true;
sta.push(pi);
while(index != ){
if(!visited[edge[index].end]){
Tarjan(edge[index].end);
exitID[pi] = min(exitID[pi],exitID[edge[index].end]);
}else if(inStack[edge[index].end]){
exitID[pi] = min(exitID[pi],visitID[edge[index].end]);
}
index = edge[index].next;
}
if(exitID[pi] == visitID[pi]){
getSonMap(pi);
}
}
int n;
int *v;
long long *f;
long long *g;
inline void init(){
readInteger(n);
v = new int[(const int)(n + )];
edge = new Edge[(const int)(n + )];
h = new int[(const int)(n + )];
visited=new boolean[(const int)(n+)];
visitID=new int[(const int)(n+)];
exitID =new int[(const int)(n+)];
inStack=new boolean[(const int)(n+)];
start = new vector<int>[(const int)(n / + )];
f = new long long[(const int)(n + )];
g = new long long[(const int)(n + )];
memset(h, , sizeof(int) * (n + ));
memset(visited,false,sizeof(boolean)*(n+));
memset(inStack,false,sizeof(boolean)*(n+));
for(int i = ,e; i <= n; i++){
readInteger(v[i]);
readInteger(e);
addEdge(e, i);
}
}
void tree_dp(int node, int last){
f[node] = v[node];
g[node] = ;
for(int i = h[node]; i != ; i = edge[i].next){
int e = edge[i].end;
if(e == last || !(visited[e])) continue;
tree_dp(e, node);
f[node] += g[e];
g[node] += max(f[e], g[e]);
}
}
#define int long long
long long *fc[];
long long *gc[];
long long** c[] = {&fc[], &fc[], &gc[], &gc[]};
int circle_dp(int index){
int result = ;
for(int i = ; i < ; i++){
*c[i] = new int[(const int)(start[index].size() + )];
memset(*c[i], , sizeof(int) * (start[index].size() + ));
}
for(int k = ; k < ; k++){
fc[k][] = (k == )?(g[start[index][]]):(f[start[index][]]);
gc[k][] = (k == )?(g[start[index][]]):(g[start[index][]]);
for(int i = ; i <= start[index].size(); i++){
fc[k][i] = gc[k][i - ] + f[start[index][i - ]];
gc[k][i] = max(gc[k][i - ], fc[k][i - ]) + g[start[index][i - ]];
}
int e = start[index][start[index].size() - ];
int s = start[index].size();
fc[k][s] = (k == )?(f[e] + gc[k][s - ]):();
gc[k][s] = (k == )?(g[e] + max(gc[k][s - ], fc[k][s - ])):();
result = max(result, fc[k][s]);
result = max(result, gc[k][s]);
}
return result;
}
#undef int
int main(){
init();
for(int i = ; i <= n; i++)
if(!visited[i])
Tarjan(i);
delete[] visitID;
delete[] exitID;
delete[] inStack;
memset(visited, true, sizeof(boolean) * (n + ));
for(int k = ; k < cc; k++)
for(int i = ; i < start[k].size(); i++){
visited[start[k][i]] = false;
}
for(int k = ; k < cc; k++)
for(int i = ; i < start[k].size(); i++)
tree_dp(start[k][i], );
delete[] visited;
long long result = ;
for(int k = ; k < cc; k++)
result += circle_dp(k);
cout<<result;
return ;
}
写得有点复杂，不过这都不重要（笑）
第一次ac省选的（水）题，好开心