HDU - 6228

这题还是蛮好的，有两种方法，一种是遍历边，一种是遍历点，但是本质其实是一样的，因为遍历边的时候最终都是用点来判断的。而且直接遍历点方便很多。

（1）遍历边：

https://blog.csdn.net/lzc504603913/article/details/78513654

（2）

遍历点：

https://blog.csdn.net/my_sunshine26/article/details/78448923

 

我用的是遍历点：

注意：

这里一定是判断num[u],而不是num[now]，因为是符合手动模拟的过程。。

 

代码：

//L
#include<stdio.h>
#include<string.h>
#include<vector>
using namespace std;
#define MAXN 200010

vector<int>V[MAXN];
int num[MAXN];//记录每个点的子节点（包括他自己）的数量
int n,k;
int ans;

void dfs(int now,int pre)
{
    int i;
    int u;

    num[now]=1;
    for(i=0;i<V[now].size();i++)
    {
        u=V[now][i];
        if(u==pre)
            continue;
        dfs(u,now);
        num[now]+=num[u];
        if(num[u]>=k&&n-num[u]>=k)
            ans++;
    }
}

int main()
{
    int i;
    int kase;
    int u,v;

    scanf("%d",&kase);
    while(kase--)
    {
        scanf("%d%d",&n,&k);
        memset(V,0,sizeof(V));
        for(i=1;i<n;i++)
        {
            scanf("%d%d",&u,&v);
            V[u].push_back(v);
            V[v].push_back(u);
        }
        memset(num,0,sizeof(num));
        ans=0;
        dfs(1,-1);
        printf("%d\n",ans);
    }
    return 0;
}