P2607 [ZJOI2008] 骑士

标签：cnt int ed st P2607 ZJOI2008 ans pair 骑士

#include<bits/stdc++.h>
//#include<windows.h>
using namespace std;
#define ll long long
const int N=1e6+1;
int n;
int h[N],nt[N*2],to[N*2];
int cnt;
void add(int x,int y)
{
    nt[cnt]=h[x];
    h[x]=cnt;
    to[cnt]=y;
    cnt++;
}
int val[N],vis[N];
int EDGE;
namespace dp
{
    ll f[N][2];
    pair < int , int > st_ed;
    void dp(int x,int fa)
    {
        f[x][1]=val[x];
        f[x][0]=0;
        for(int i=h[x]; ~i; i=nt[i])
        {
            int y=to[i];
            if(y==fa||i==EDGE||i==(EDGE^1))
                continue;
            dp(y,x);
            f[x][1]+=f[y][0];
            f[x][0]+=max(f[y][0],f[y][1]);
        }
        return;
    }
    ll work(pair < int , int > x)
    {
        st_ed=x;
        ll ans=0;
        dp(st_ed.first,-1);
        ans=max(ans,f[st_ed.first][0]);
        dp(st_ed.second,-1);
        ans=max(ans,f[st_ed.second][0]);
        //cout<<ans<<endl;
        return ans;
    }
}
namespace tree
{
    int v[N];
    pair < int , int > st_ed;
    void dfs(int x,int id)
    {
        vis[x]=1;
        for(int i=h[x]; ~i; i=nt[i])
        {
            int y=to[i];
            if(i==(id^1))continue;
            if(vis[y])
            {
                st_ed=make_pair(x,y);
                EDGE=i;
            }
            else{
                dfs(y,i);
            }
        }
    }
     pair < int , int > work(int i)
    {
        st_ed=make_pair (-1,-1);
        dfs(i,-1);
        //cout<<st_ed.first<<" "<<st_ed.second<<endl;
        //cout<<EDGE<<endl;
        return st_ed;
    }
}
ll ans=0;
signed main()
{
    //freopen("text.in","r",stdin);
    memset(h,-1,sizeof(h));
    scanf("%d",&n);
    for(int i=1,x; i<=n; i++)
    {
        scanf("%d%d",&val[i],&x);
        add(x,i),add(i,x);
    }
    for(int i=1; i<=n; i++)
    {
        if(vis[i])continue;
        ans+=dp::work(tree::work(i));
    }
    printf("%lld",ans);
}

标签：cnt,int,ed,st,P2607,ZJOI2008,ans,pair,骑士
From： https://www.cnblogs.com/dadidididi/p/16816619.html