洛谷P2607 [ZJOI2008]骑士基环树动归

Code:

#include<algorithm>

#include<cstdio>

#include<algorithm>

#include<cstring>

using namespace std;

typedef long long ll;

const int maxn=1000000+233;

const int N=1000000+233;

int A[N],B[N];

ll G[N],F[N];

int head[maxn*2],nex[maxn*2],to[maxn*2],val[maxn],vis[maxn];

int cnt,num,root;

struct Circle{

    int p[maxn];

    void init(){

        for(int i=1;i<maxn-12;++i)p[i]=i;

    }

    int find(int x){

        if(p[x]==x)return x;

        else return p[x]=find(p[x]);

    }

    int query(int x,int y){

        int a=find(x);int b=find(y);

        if(a!=b)p[a]=b;

        if(a==b)return 1;

        return 0;

    }

}S;

void add_edge(int u,int v){

    nex[++cnt]=head[u],to[cnt]=v,head[u]=cnt;

}

void dfs(int u,int fa,int c){

	G[u]=val[u],F[u]=0,vis[u]=1;

	for(int v=head[u];v;v=nex[v])

		if(to[v]!=fa){

			dfs(to[v],u,c);

			G[u]+=F[to[v]];

			F[u]+=max(F[to[v]],G[to[v]]);

		}

}

int main(){

    ll ans=0;

    S.init();

    int n;

    scanf("%d",&n);

    for(int i=1;i<=n;++i){

        int a,b;scanf("%d%d",&a,&b);

        val[i]=a;

        int flag=S.query(i,b);

        if(flag==0){

            add_edge(i,b);

            add_edge(b,i);

        }

        if(flag==1)A[++num]=b,B[num]=i;

    }

    for(int i=1;i<=num;++i){

        int a=A[i],b=B[i];

        ll sum1,sum2;

        root=b;dfs(b,-1,a);sum1=F[b];

        root=a;dfs(a,-1,b);sum2=F[a];

        ans+=max(sum1,sum2);

    }

    for(int i=1;i<=n;++i)

    	if(!vis[i]){

    		dfs(i,-1,-2);

    		ans+=max(F[i],G[i]);

    	}

    printf("%lld",ans);

    return 0;

}

巴特西

洛谷P2607 [ZJOI2008]骑士基环树动归

最新文章

热门文章

巴特西

洛谷P2607 [ZJOI2008]骑士 基环树动归

最新文章

热门文章

洛谷P2607 [ZJOI2008]骑士基环树动归