【洛谷P2607】[ZJOI2008]骑士

骑士

这道题一看，似乎和舞会是一样的，然而它并没有保证是一棵树

但是，对于每个连通块，必有相同的点数和边数，这样的图一定是一棵树上加一条边

这条边一定回使图中形成一个环，这种图貌似叫“基环树”。。

我们只要将不同的连通块分开处理，最后相加即可

对于一个基环树，只要找到环上的一条边，把它“拆掉”，分别从两个顶点dp一下就行了，

由于一条边的两个顶点不能同时选，就将f[u][0]与f[v][0]取一个max即可

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

using namespace std;

#define MAXN 1000100

int n,value[MAXN],Head[MAXN],num=,root1,root2,cut=-;

long long dp[MAXN][],ans;

bool vis[MAXN];

struct NODE{

    int to,next;

} e[MAXN<<];

inline int read(){

    int x=; char c=getchar();

    while(c<''||c>'') c=getchar();

    while(''<=c&&c<='') { x=(x<<)+(x<<)+c-''; c=getchar(); }

    return x;

}

inline void add(int x,int y){

    e[++num].to=y;

    e[num].next=Head[x];

    Head[x]=num;

}

void dfs(int t,int last){　　//找环

    vis[t]=;

    for(int i=Head[t];i;i=e[i].next)

     if(e[i].to!=last){

        if(!vis[e[i].to]) dfs(e[i].to,t);

        else { cut=i; root1=t; root2=e[i].to; }

    }

}

void solve(int t,int last)　　//舞会

{

    dp[t][]=;

    dp[t][]=value[t];

    for(int i=Head[t];i;i=e[i].next)

     if(e[i].to!=last&&i!=cut&&i!=(cut^))

      {

        int v=e[i].to;

        solve(v,t);

        dp[t][]+=max(dp[v][],dp[v][]);

        dp[t][]+=dp[v][];

      }

}

int main()

{

    scanf("%d",&n);

    int y;

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

        scanf("%d%d",&value[i],&y);

        add(i,y); add(y,i);

    }

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

     if(!vis[i]){

        dfs(i,-);

        solve(root1,-);

        long long t=dp[root1][];

        solve(root2,-);

         ans+=max(t,dp[root2][]);

     }

    printf("%lld\n",ans);

    return ;

}

巴特西

【洛谷P2607】[ZJOI2008]骑士

最新文章

热门文章