Tree

Time Limit: 1000MS		Memory Limit: 30000K
Total Submissions: 3506		Accepted: 1204

Consider a tree with N vertices, numbered from 1 to N. Add, if it is possible, a minimum number of edges thus every vertex belongs to exactly one cycle.

The input has the following structure: 

N 

x(1) y(1) 

x(2) y(2) 

... 

x(N-1) y(n-1) 

N (3 <= N <=100) is the number of vertices. x(i) and y(i) (x(i), y(i) are integers, 1 <= x(i), y(i) <= N) represent the two vertices connected by the i-th edge. 

The output will contain the value -1 if the problem doesn't have a solution, otherwise an integer, representing the number of added edges.

7

1 2

1 3

3 5

3 4

5 6

5 7

2

field=source&key=Romania+OI+2002" style="text-decoration:none">Romania OI 2002

树形DP啊，可是知道也推不出公式来，。无奈的看了解题报告。发现前方的道路还非常漫长啊，这思路神了

http://www.cnblogs.com/vongang/archive/2012/08/12/2634763.html

#include <iostream>

#include <cstring>

#include <cstdio>

#include <algorithm>

#include <cstdlib>

#include <cmath>

#define N 110

#define INF 150

using namespace std;

struct num

{

    int y,next;

}a[N*N];

int b[N],Top;

int dp[N][3];

bool ch[N];

int main()

{

    //freopen("data.txt","r",stdin);

    void addeage(int x,int y);

    void dfs(int x);

    int n;

    while(scanf("%d",&n)!=EOF)

    {

        Top = 0;

        memset(b,-1,sizeof(b));

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

        {

            int x,y;

            scanf("%d %d",&x,&y);

            addeage(x,y);

            addeage(y,x);

        }

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

        {

            dp[i][0] = dp[i][1] = dp[i][2] = INF;

        }

        memset(ch,false,sizeof(ch));

        dfs(1);

        //cout<<dp[3][1]<<endl;

        if(dp[1][0]==INF)

        {

            printf("%d\n",-1);

        }else

        {

            printf("%d\n",dp[1][0]);

        }

    }

    return 0;

}

void addeage(int x,int y)

{

    a[Top].y = y;

    a[Top].next = b[x];

    b[x] = Top++;

}

void dfs(int x)

{

    ch[x] = true;

    bool uv = true;

    for(int i=b[x];i!=-1;i=a[i].next)

    {

        int y = a[i].y;

        if(!ch[y])

        {

            uv = false;

            break;

        }

    }

    if(uv)

    {

        dp[x][1] =0;

        return ;

    }

    dp[x][1] = 0;

    int sum = 0;

    bool ch2[N];

    memset(ch2,false,sizeof(ch2));

    for(int i=b[x];i!=-1;i=a[i].next)

    {

        int y =  a[i].y;

        if(!ch[y])

        {

            dfs(y);

            ch2[y] = true;

            dp[x][1]+=dp[y][0];

            sum+=dp[y][0];

        }

    }

    if(dp[x][1]>=INF)

    {

        dp[x][1] = INF;

    }

    for(int i=b[x];i!=-1;i=a[i].next)

    {

        int y = a[i].y;

        if(!ch2[y])

        {

            continue;

        }

        int w = sum-dp[y][0]+min(dp[y][1],dp[y][2]);

        if(w>=INF)

        {

            w = INF;

        }

        dp[x][2] = min(dp[x][2],w);

        w = sum-dp[y][0] + dp[y][2]+1;

        if(w>=INF)

        {

            w = INF;

        }

        dp[x][0] = min(dp[x][0],w);

    }

    for(int i=b[x];i!=-1;i=a[i].next)

    {

        int y1 = a[i].y;

        if(!ch2[y1])

        {

            continue;

        }

        for(int j=b[x];j!=-1;j=a[j].next)

        {

            int y2 = a[j].y;

            if(y1==y2||!ch2[y2])

            {

                continue;

            }

            int w = sum-dp[y1][0] - dp[y2][0] + min(dp[y1][1],dp[y1][2]) + min(dp[y2][1],dp[y2][2])+1;

            if(w>=INF)

            {

                w = INF;

            }

            dp[x][0] = min(dp[x][0],w);

        }

    }

}