Codeforces

Luogu

分析

假设现在在考虑 $u$ 节点,子树中传上来了 $s$ 个集合,$u$ 到第 $i$ 个集合中最深的节点的距离为 $l_i$。

将 $l_i$ 从小到大排序,找到一个最大的 $p$ 满足 $l_{p-1}+l_p\leq k$。显然把 $l_1,l_2,\cdots l_p$ 放到一个集合里,$l_{p+1},\cdots l_s$ 分别放到 $1$ 个集合里是最优的。于是把答案加上 $s-p$,再将 $l_p$ 传上去。

那么直接 DFS 做这个过程就好了。最后最上面那个集合是没有加到答案里的,所以还要加上 $1$。

另外注意要找一个度数 $\geq 2$ 的节点作为根,不然会出现一些问题。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=1000000+10;

int n,k;

struct edge { int v,nxt; } e[N<<1];
int head[N],deg[N];
inline void addEdge(int u,int v) {
    static int cnt=0;
    e[++cnt]=(edge){v,head[u]},head[u]=cnt;
}

vector<int> vec; int f[N],ans=0;
inline void dfs(int u,int fa) {
    for (re int i=head[u];i;i=e[i].nxt)
        if (e[i].v!=fa) dfs(e[i].v,u);
    vec.clear();
    for (re int i=head[u];i;i=e[i].nxt)
        if (e[i].v!=fa) vec.push_back(f[e[i].v]+1);
    sort(vec.begin(),vec.end());
    re int p=vec.size()-1;
    for (;p>0;--p,++ans)
        if (vec[p-1]+vec[p]<=k) break;
    f[u]=vec.empty()?0:vec[p];
}

int main() {
    n=read(),k=read();
    for (re int i=1;i<n;++i) {
        int u=read(),v=read();
        addEdge(u,v),++deg[v];
        addEdge(v,u),++deg[u];
    }
    for (re int i=1;i<=n;++i)
        if (deg[i]>1) { dfs(i,0); break; }
    printf("%d\n",ans+1);
    return 0;
}
最后修改:2019 年 10 月 14 日 09 : 14 PM