LA 3902 Network

浏览数：41 / 时间：2015年06月09日

　　贪心的思想吧，对于每一个还没被覆盖到的叶子节点，最优的选择就是他的k级祖先(节点的父亲为1级祖先)。

　　记录下各深度的叶子节点，这对于这些节点选择一个最优的祖先节点，然后从选出的这个祖先节点向外扩展，把该点能覆盖到的叶子节点全都标记。按深度从深到浅使每个叶子节点都被覆盖后，既是ans

#include <map>
#include <cmath>
#include <cstdio>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 1005;
vector<int>f[maxn],depth[maxn];
int fa[maxn],vis[maxn],flag[maxn];
int n,s,k;
void build(int rt,int d)
{
    vis[rt] = 1;
    int len = f[rt].size();
    if(len==1 && d>k)depth[d].push_back(rt);
    for(int i = 0;i<len;++i)
    {
        int u = f[rt][i];
        if(vis[u])continue;
        fa[u] = rt;
        build(u,d+1);
    }
}
void dfs(int rt,int d)
{
    vis[rt] = 1;
    int len = f[rt].size();
    if(len==1 && d<=k){flag[rt]=1;return;}
    for(int i = 0;i<len;++i)
    {
        int u = f[rt][i];
        if(!vis[u])dfs(u,d+1);
    }
}
int main()
{
//    freopen("in.txt","r",stdin);
    int T;scanf("%d",&T);
    while(T--)
    {
        memset(f,0,sizeof(f));
        memset(vis,0,sizeof(vis));
        memset(flag,0,sizeof(flag));
        memset(depth,0,sizeof(depth));
        scanf("%d%d%d",&n,&s,&k);
        for(int i = 1;i<n;++i)
        {
            int u,v;scanf("%d%d",&u,&v);
            f[u].push_back(v);
            f[v].push_back(u);
        }
        build(s,0);
        int ans = 0;
        for(int i = n;i>k;--i)
        {
            int len = depth[i].size();
            for(int j = 0;j<len;++j)
            {
                int u = depth[i][j];
                if(flag[u])continue;
                memset(vis,0,sizeof(vis));
                for(int i = 0;i<k;++i)u = fa[u];
                dfs(u,0);
                ans++;
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}