UVa:1267 Network

자기 마음대로 생각하던 생각이 뜻밖에도 바뀌었구나, 정말 눈물이 얼굴에 가득하구나...
우선 뿌리가 없는 나무가 뿌리가 있는 나무로 바뀌어야 한다. 이 류여가의 첫 번째 책에는 있다.그리고 dfs는 모든 잎 결점을 취하고 그 깊이에 따라 큰 것부터 작은 것까지 정렬합니다.이렇게 순서대로 각 잎결점을 판단하려면 먼저 이 잎결점에 대한 접근과 그 거리 k 이내의 모든 결점은 서버인지 아닌지를 보고 없으면 이 잎결점에서 위로 아버지 결점을 따라 두루 돌아다니며 거리 k의 그 결점을 선택하여 서버를 배치해야 한다.

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <vector>
#include <queue>
#include <map>
#include <algorithm>
#define ll long long
#define INF 2139062143
#define inf -2139062144
#define MOD 20071027
#define MAXN 1005
using namespace std;
struct Tree
{
    int father;
    vector<int> child;
};
struct Node
{
    int num,deep;
};
vector<Node> vec;
int n,k,s;
Tree tree[MAXN];
bool flag[MAXN],vis[MAXN];
bool gl[MAXN][MAXN],leave[MAXN];
int ans;
void Init()
{
    for(int i=0; i<=n; ++i)
    {
        tree[i].child.clear();
        tree[i].father=0;
    }
    vec.clear();
    memset(gl,0,sizeof(gl));
    memset(leave,0,sizeof(leave));
}
void getnode(int u,int d)
{
    if(tree[u].child.size()==0)
    {
        vec.push_back(Node {u,d});
        leave[u]=true;
    }
    else
    {
        for(int i=0; i<tree[u].child.size(); ++i)
            getnode(tree[u].child[i],d+1);
    }
}
bool search(int u,int d)
{
    if(d<=k)
    {
        vis[u]=true;
        if(flag[u]) return true;
        for(int i=0; i<tree[u].child.size(); ++i)
            if(!vis[tree[u].child[i]]&&search(tree[u].child[i],d+1)) return true;
        if(!vis[tree[u].father]&&search(tree[u].father,d+1)) return true;
        return false;
    }
    return false;
}
bool makeflag(int u,int d)
{
    if(d<=k)
    {
        if(d==k)
        {
            flag[u]=true;
            return true;
        }
        if(makeflag(tree[u].father,d+1)) return true;
        return false;
    }
    return false;
}
bool cmp(Node a,Node b)
{
    return a.deep>b.deep;
}

void maketree(int u,int f)
{
    tree[u].father=f;
    for(int i=1; i<=n; ++i)
        if(gl[u][i]&&i!=f)
        {
            tree[u].child.push_back(i);
            maketree(i,u);
        }
}
int main()
{
    int T;
    //freopen("asdf.txt","w",stdout);
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        scanf("%d%d",&s,&k);
        Init();
        for(int i=1; i<n; ++i)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            gl[x][y]=gl[y][x]=true;
        }
        maketree(s,-1);
        ans=0;
        getnode(s,0);
        sort(vec.begin(),vec.end(),cmp);
        memset(flag,0,sizeof(flag));
        flag[s]=true;
        for(int i=0; i<vec.size(); ++i)
        {
            memset(vis,0,sizeof(vis));
            if(!search(vec[i].num,0))
            {
                makeflag(vec[i].num,0);
                ans++;
            }
        }
        printf("%d
",ans);
    }
    return 0;
}