about 4 years ago

题意

给定一个n个节点的无权树,要在这棵树上选一些点建什么站,使得每个节点到他最近的站的距离不超过k

思考

任意两个站之间的距离 那么我们可以令第节点离他最近站的距离为

  1. 为叶子,考虑到离最近站最远的距离为k,则 可以保证最优

  2. 只有1个孩子

  3. 有至少两个孩子 , 设 是它的孩子节点中, 最小的, 是孩子节点中最大的. 那么,如果 , 则该节点可以被自己子树上的服务站照顾到,所以它到最近的站距离是p+1。 因为很显然 ,所以这个,所以这个站就没有必要放置服务站了. 反之,若 不成立,我们不妨就把他的 设成

  4. 如果 ,则该点需要新建一个站

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <climits>
using namespace std;

typedef int arr[500010];
const int INF=1000000000;
int tot , n , k , mind , maxd , cnt;
arr head,pnt,next,rank,ans,vis;

inline void add(int a,int b) {
    next[++tot] = head[a]; head[a] = tot; pnt[tot] = b; 
}
inline void DFS(int x,int fa)
{
    int flag = 0; vis[x] = 1;
    mind = INF; maxd = -INF;
    for (int i = head[x];i;i = next[i]) 
        if (!vis[pnt[i]])
            {
                DFS(pnt[i],x) , flag ++; 
                maxd = max(maxd , rank[pnt[i]]);
                mind = min(mind , rank[pnt[i]]);
            }
    if (!flag) rank[x] = k + 1;
    else if (flag == 1) rank[x] = mind + 1;
    else if (flag >= 2) {
            if (mind + maxd + 2 <= 2 * k + 1) rank[x] = mind + 1; else rank[x] = maxd + 1;
        }
    if (rank[x] == 2 * k + 1) rank[x] = 0 , ans[x] = 1 , ++cnt;
}

int main()
{
    freopen("280.in","r",stdin);
    freopen("280.out","w",stdout);
    int a,b;
    scanf("%d%d",&n,&k);
    for (int i = 1;i < n;i++) 
        scanf("%d%d",&a,&b) , add(a,b) , add(b,a);
    
    DFS(1,0);  
    printf("%d\n",cnt); 
    for (int i = 1;i <= n;i++)
         if (ans[i] == 1 || (i == 1 && rank[1] > k)) printf("%d ",i);
    return 0; 
}
← 关于大组合数的取模问题 关于扩展Bs_Gs问题的应用 →
 
comments powered by Disqus