记录编号	593835	评测结果	AAAAAAAAAA
题目名称	[ZJOI 2008] 骑士	最终得分	100
用户昵称	徐诗畅	是否通过	通过
代码语言	C++	运行时间	0.929 s
提交时间	2024-09-17 16:02:47	内存使用	15.64 MiB

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e6+5;
int n,a[N],head[N],cnt=1,vis[N],ans,x1,x2,ed,dp[N][5];
struct edge{
    int v,next;
}e[N]; 
void addedge(int u,int v){
    e[++cnt].v=v;
    e[cnt].next=head[u];
    head[u]=cnt;
} 
void dfs(int u,int fa){
    vis[u]=1;
    for(int i = head[u];i;i=e[i].next){
        int v=e[i].v;
        if(v==fa) continue;
        if(vis[v]){
            x1=u; x2=v; ed=i; continue;
        }
        dfs(v,u);
    }
}
void DP(int u,int fa){
    dp[u][0]=0; dp[u][1]=a[u];
    for(int i = head[u];i;i=e[i].next){
        int v=e[i].v;
        if(v==fa||i==ed||(i^1)==ed) continue;
        DP(v,u);
        dp[u][0]+=max(dp[v][0],dp[v][1]);
        dp[u][1]+=dp[v][0];
    }
}
signed main(){
    freopen("bzoj_1040.in","r",stdin);
    freopen("bzoj_1040.out","w",stdout);
    scanf("%lld",&n);
    for(int i = 1;i<=n;i++){
        int x,y; scanf("%lld%lld",&x,&y);
        addedge(i,y); addedge(y,i);
        a[i]=x;
    }
    for(int i = 1;i<=n;i++){
        if(!vis[i]){
            dfs(i,-1); DP(x1,-1);
            int tmp=dp[x1][0];
            DP(x2,-1);
            ans+=max(tmp,dp[x2][0]);
        }
    }
    printf("%lld",ans);
    return 0;
}