트리 DP

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

#include<iostream>

#include<cstdio>

#include<cstring>

#include<queue>

#include<algorithm>

#define inf 10000000

#define Maxn 1100010

using namespace std;

int vi[Maxn],head[Maxn],ans,e,dp[Maxn][2];

struct Edge{

    int u,v,next,val;

}edge[Maxn*2];

void init()

{

    e=0;

    ans=0;

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

    memset(dp,0,sizeof(dp));

    memset(vi,0,sizeof(vi));

}

void add(int u,int v)

{

    edge[e].u=u,edge[e].v=v,edge[e].next=head[u],head[u]=e++;

    edge[e].v=u,edge[e].u=v,edge[e].next=head[v],head[v]=e++;

}

void dfs(int u)

{

    int i,v;

    vi[u]=1;

    int sum1=0,num1=0,sum2=0,num2=0,sz=0;

    for(i=head[u];i!=-1;i=edge[i].next){

        v=edge[i].v;

        if(vi[v]) continue;

        dfs(v);

        if(dp[v][0]<=dp[v][1]){

            sum1+=dp[v][0];

            num1++;

        }else if(dp[v][0]<=dp[v][1]+1){

            sum2+=dp[v][0];

            num2++;

        }else {

            sum1+=dp[v][1]+2;

        }

        sz++;

    }

    //if(u==1) printf("%d %d %d %d
",num1,sum1,num2,sum2);

    if(sz==0) return ;

    if(sz==1){

        dp[u][0]=sum1+sum2;

        dp[u][1]=inf;

        return ;

    }

    if(num1>=1){

        dp[u][0]+=sum1+sum2+num2+(num1-1)*2;

        if(num1>=2){

            dp[u][1]+=sum1+sum2+(num1-2)*2+num2;

        }

        else {

            dp[u][1]+=sum1+sum2+num2;

        }

        return ;

    }

    if(num2>=1){

        dp[u][0]+=sum1+sum2+(num2-1);

        if(num2>=2){

            dp[u][1]+=sum1+sum2+(num2-2);

        }

        else dp[u][1]+=sum1+sum2;

        return ;

    }

    dp[u][0]+=sum1+sum2;

    dp[u][1]+=sum1+sum2;

}

int main()

{

    int t,n,i,j,u,v;

    scanf("%d",&t);

    while(t--){

        init();

        scanf("%d",&n);

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

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

            add(u,v);

        }

        dfs(1);

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

          //  printf("%d %d %d 
",i,dp[i][0],dp[i][1]);

        printf("%d
",min(dp[1][0],dp[1][1])+1);

    }

    return 0;

}