记录编号	478414	评测结果	AAAAAAAAAE
题目名称	[ZJOI 2008] 骑士	最终得分	90
用户昵称	test	是否通过	未通过
代码语言	C++	运行时间	0.477 s
提交时间	2017-12-11 13:21:32	内存使用	10.49 MiB

#include<bits/stdc++.h>
#define ll long long
#define RG register
#define il inline
#define N 1000010
using namespace std;
struct ed{int nxt,to;}e[N];
int head[N],tot,n,fa[N],cnt;bool vis[N];
ll g[N],f[N],val[N];
pair<int,int> a[N];
int find(int x){if(fa[x]!=x)fa[x]=find(fa[x]);return fa[x];}
void LINK(int u,int v){e[tot].nxt=head[u];e[tot].to=v;head[u]=tot++;}
void link(int u,int v){LINK(u,v),LINK(v,u);}
void DP(int u,int faa){
  f[u]=val[u],g[u]=0;
  for(int i=head[u];i!=-1;i=e[i].nxt){
    int v=e[i].to;if(v==faa)continue;
    DP(v,u);
    f[u]+=g[v],g[u]+=max(f[v],g[v]);
  }
}
int main(){
  freopen("bzoj_1040.in","r",stdin);
  freopen("bzoj_1040.out","w",stdout);
  scanf("%d",&n);int v,x,y;
  memset(head,-1,sizeof(head));
  for(int i=1;i<=n;++i)fa[i]=i;
  for(int u=1;u<=n;++u){
    scanf("%lld%d",&val[u],&v);
    x=find(u),y=find(v);
    if(x!=y)link(u,v),fa[x]=fa[y];
    else a[++cnt]=make_pair(u,v);
  }ll ans(0),temp;
  for(int i=1;i<=cnt;++i){
    DP(a[i].first,a[i].first);temp=g[a[i].first];
    DP(a[i].second,a[i].second);temp=max(temp,g[a[i].second]);
    ans+=temp;   
  }printf("%lld",ans);
  return 0;
}