【题目链接】 http://www.lydsy.com/JudgeOnline/problem.php?id=1040
【题目大意】
给出环套外向树森林，求最大权独立集。
【题解】
我们对于每个连通块，找到环上的一条边拆开，对于边的两端分别做树形DP，
假设两端点位x和y，那么不包含x的dp值涵盖了是否包含y两种情况，
同理，以y为根的也是，因为边的两端不能同时取到，因此对于两者取最大值即可。
代码中f[x]表示包含x的dp值，g[x]表示不包含x的dp值。
【代码】
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long LL;
const int N=1000010;
vector<int> v[N],id[N];
LL g[N],f[N],ans;
int ban,n,c[N],x,vis[N],root,_root,idn=0;
void dfs(int x,int fx){
vis[x]=1;
for(int i=0;i<v[x].size();i++){
int y=v[x][i];
if(y==fx)continue;
if(!vis[y])dfs(y,x);
else{root=y;_root=x;ban=id[x][i];}
}
}
void TreeDP(int x,int fx){
f[x]=c[x],g[x]=0;
for(int i=0;i<v[x].size();i++){
int y=v[x][i];
if(y==fx)continue;
if(id[x][i]==ban||id[x][i]==(ban^1))continue;
TreeDP(y,x);
f[x]+=g[y]; g[x]+=max(f[y],g[y]);
}
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d%d",&c[i],&x);
v[x].push_back(i);
id[x].push_back(idn++);
v[i].push_back(x);
id[i].push_back(idn++);
}
for(int i=1;i<=n;i++){
if(!vis[i]){
dfs(i,-1);
TreeDP(root,-1);
LL tmp=g[root];
TreeDP(_root,-1);
tmp=max(tmp,g[_root]);
ans+=tmp;
}
}printf("%lld\n",ans);
return 0;
}