学步园

题意：一个树减去一条边，或者加上一条边的费用都是1，问把这棵树改成一个圆的最小费用。

一个树形dp，不会dp的菜鸟，，，，各种分类讨论。。。

#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <list>
#include <deque>
#include <string>

#define LL long long
#define DB double
#define SI(a) scanf("%d",&a)
#define SD(a) scanf("%lf",&a)
#define SS(a) scanf("%s",a)
#define SF scanf
#define PF printf
#define MM(a,b) memset(a,b,sizeof(a))
#define REP(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
#define REPD(i,a,b) for(int (i)=(a);(i)>(b);(i)--)
#define N 1000009
#define INF 0x3f3f3f3f
#define EPS 1e-8
#define bug puts("bug")
using namespace std;
vector<int> L[N];
int n,ans;
int v[N];
int solve(int k)
{
    if(v[k]) return 0;
    v[k] = 1;
    int s =0;
    REP(i,0,(int)L[k].size())
    {
        int to = L[k][i];
        s += solve(to);
    }
    if(k==1)
    {
        if(s==0)
        {
            ans++;
            return 0;
        }
        if(s==1)
        {
            ans++;return 0;
        }
        if(s==2)
        {
            ans++;///ans+=2;不需要将该节点与父亲节点的边删掉，so，只需要加一次，谢谢qw4990指出错误。
            return 0;
        }
        if(s>2)
        {
            ans += (s-2)*2+1;
            return 0;
        }
    }else
    {
        if(s==0) return 1;
        if(s==1) return 1;
        if(s==2)
        {
            ans+=2;
            return 0;
        }
        if(s>2)
        {
            ans += (s-2)*2+2;
            return 0;
        }
    }
    return -1;
}
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
    #endif
    int cas;SI(cas);
    while(cas--)
    {
        SI(n);
        REPD(i,n+5,-1) L[i].clear();
        int a,b;
        MM(v,0);
        ans = 0;
        REP(i,1,n)
        {
            SI(a);SI(b);
            L[a].push_back(b);
            L[b].push_back(a);
        }
        solve(1);
        PF("%d\n",ans);
    }
    return 0;
}