hdu 4714 Tree2cycle

乱搞题，要求用最少的操作把一颗树转化成一个环。其实就是把树分成最少的链，然后连接起来即可，仔细观察树的话会发现，一般一个点的度如果大于1的话，该点必然要断开一些连接，因为最终每个点的度都是2， 然后就是看点上断开那些连接了，其实，如果一个节点的除去父亲节点如果度大于1的话，断开与父亲节点的那条边必然是一种正解。。。于是问题就解决了，只需一遍dfs即可。在杭电交注意加上挂。。。不然会爆栈。。。

#pragma comment(linker,"/STACK:102400000,102400000")
#include<algorithm>
#include<iostream>
#include<cstring>
#include<vector>
#include<cstdio>
#include<cmath>

#define LL long long
#define PB(a) push_back(a);
#define CLR(a, b) memset(a, b, sizeof(a))

using namespace std;

const int N = 1111111;

vector<int> E[N];
int ans;

int dfs(int u, int fa)
{
    int v, i, hav = 0;
    for(i = 0; i < E[u].size(); i ++)
    {
        v = E[u][i];
        if(v != fa) hav += dfs(v, u);
    }
    if(fa == -1 && hav > 1) ans += hav - 2;
    else if(hav > 1)
    {
        ans += hav - 1;
        return 0;
    }
    return 1;
}

int main()
{
    int n, t, i, j, u, v;
    scanf("%d", &t);
    while(t --)
    {
        scanf("%d", &n);
        for(i = 0; i <= n; i ++) E[i].clear();
        for(i = 1; i < n; i ++)
        {
            scanf("%d%d", &u, &v);
            E[u].PB(v);
            E[v].PB(u);
        }
        ans = 1;
        dfs(1, -1);
        printf("%d\n", ans * 2 - 1);
    }
    return 0;
}