HDU 4714 Tree2cycle 找规律

假设最少删除的边的个数为cost，显然，最终答案即为cost+cost+1 (因为删除一条边，就会增加一个链，所以删除cost条边后，就会有cost+1条链，将这cost+1条链连接起来的代价为cost+1, 删除cost条边的代价为cost，所以总代价为cost+cost+1)

求最少删除的边数：

首先我们定义一棵子树中的链不能以该子树的根为端点，以下提到的所有链均必须满足这个条件。

设一棵以节点i为根的子树中，叶子节点的个数为duan，并设i的父亲为fa。

那么，这棵子树至少会分割成duan-1条链（以其中两个叶子为端形成一条链，剩下的一个叶子对应一条链）。

DFS，对于某棵以节点i为根的子树，如果子树中叶子节点个数<=1，那么在这棵子树内无法分割成完整的一条链（分割成完整的链至少需要两个叶子），相当于对fa而言，节点i依然是一个叶子。

如果子树中有>=2个叶子，那么这棵子树内可以分割成完整的duan-1条链，相当于对fa而言，删掉节点i及以i为根的子树。

PS1.对于没有fa的节点特殊判断一下。

PS2.手动扩栈

#pragma comment(linker, "/STACK:102400000,102400000")

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <algorithm>

#include <vector>

using namespace std;

const int MAXN = ;

struct node

{

    int v;

    int next;

};

int n;

node D[MAXN<<];

int head[MAXN];

int cost, EdgeN;

void AddEdge( int u, int v )

{

    D[EdgeN].v = v;

    D[EdgeN].next = head[u];

    head[u] = EdgeN++;

    return;

}

int DFS( int cur, int fa )

{

    int duan = ;

    for ( int i = head[cur]; i != -; i = D[i].next )

    {

        if ( D[i].v != fa )

            duan += DFS( D[i].v, cur );

    }

    if ( duan <  ) return ;

    else

    {

        if ( cur ==  ) cost += duan - ;   //如果是根节点

        else cost += duan - ;

        return ;

    }

}

int main()

{

    int T;

    scanf( "%d", &T );

    while ( T-- )

    {

        scanf( "%d", &n );

        memset( head, -, sizeof(int)*(n+) );

        EdgeN = ;

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

        {

            int u, v;

            scanf( "%d%d", &u, &v );

            AddEdge( u, v );

            AddEdge( v, u );

        }

        cost = ;

        DFS( , - );

        int ans = cost +  + cost;

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

    }

    return ;

}

巴特西

HDU 4714 Tree2cycle 找规律

最新文章

热门文章