题目描述

Description

Input

Output

Sample Input

1
7
1 2
2 3
2 4
4 6
5 6
6 7

Sample Output

3

题目分析

题目大意 让你用最少的链 来覆盖整棵树
树形DP
表示覆盖x的子树 x是一条链的端点 的最少树链数
表示覆盖x的子树 x不是一条链的端点 的最少树链数
那么的情况：x可以和任意一个儿子链接 并且 这个儿子是一条链的端点
那么的情况：如果自己的儿子数量小于2 那么附为极大值 否则 可以任选两个儿子进行连接 并且这两个儿子都是某条链的端点
注意一下叶子结点的初始值

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,t;
int tot,head[10100],net[20200],to[20200];
int f[10100],g[10100],in[10100];
void init() 
{ 
    tot=0,memset(head,0,sizeof head); 
    memset(f,0x3f,sizeof f);
    memset(g,0x3f,sizeof g);
}
void add(int x,int y) { net[++tot]=head[x],head[x]=tot,to[tot]=y; }
void dfs(int x,int temp)
{
    for(int i=head[x];i;i=net[i]) if(to[i]!=temp) dfs(to[i],x);
    int cnt=0,sum=0,tmp=0x3f3f3f3f,nmp=0x3f3f3f3f;
    for(int i=head[x];i;i=net[i]) if(to[i]!=temp) cnt++;
    if(!cnt) { f[x]=1,g[x]=0x3f3f3f3f; return ; }
    for(int i=head[x];i;i=net[i]) if(to[i]!=temp)
    {
        sum+=min(g[to[i]],f[to[i]]);
        int c=max(0,f[to[i]]-g[to[i]]);
        if(c<=tmp) nmp=tmp,tmp=c;
        else if(c<=nmp) nmp=c;
    }
    f[x]=min(sum+1,sum+tmp);
    if(cnt<2) g[x]=0x3f3f3f3f;
    else g[x]=sum+tmp+nmp-1;
}
void work()
{
    init();
    scanf("%d",&n);
    for(int x,y,i=1;i<n;i++)
        scanf("%d%d",&x,&y),add(x,y),add(y,x);
    dfs(1,0);
    printf("%d\n",min(f[1],g[1]));
}
int main()
{
    scanf("%d",&t);
    while(t--) work();
}