题意

你有一颗 个节点的有根树(以 号节点为根)，求最少加入多少条边之后使得根节点（即 号节点）到这棵树上任意一点的距离不大于 。

分析

考虑一种贪心，如果一个节点 到根的距离大于 的话，那么我们就从根节点连一条边到 节点的父亲 。

来考虑正确性的证明，一个节点 到根的距离如果大于了 ，那么只会有两种方式连边 直接连向 。 连向他的父亲节点 。

我们分两种情况讨论：

如果 的父亲节点 除了 以外还有别的子节点，那么连向父亲节点 也可以同时覆盖其他儿子。

如果 没有其他儿子，那么连向 可以使得根节点到 的距离也减小，虽然 可能满足距离小于等于 ，但这样一定不劣。

所以我们只需要每次找最远的点并连接根节点和它的父亲就好了。树上解决就好了。

代码

#include<bits/stdc++.h>
#define ll long long
const int N=2e5+5,INF=0x3f3f3f3f,mod=998244353;
using namespace std;

int n,cnt;
int head[N],f[N];
bool vis[N];
struct node
{
    int to,nxt;
}e[N<<1];
struct node1
{
    int num,dep;
}p[N<<1];

inline int read()
{
    register int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
    while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return x*f;
}

int qpow(int a,int b)
{
    int ans=1;
    while(b){if(b&1) ans=ans*a%mod;a=a*a%mod;b>>=1;}
    return ans;
}

bool cmp(node1 a,node1 b)
{
    return a.dep>b.dep;
}

void add(int u,int v)
{
    e[++cnt].nxt=head[u];
    e[cnt].to=v;
    head[u]=cnt;
}

void bfs(int rt)
{
    queue <int> q;
    p[rt].dep=0;p[rt].num=rt;
    q.push(rt);
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        for(int i=head[u];i;i=e[i].nxt)
        {
            int y=e[i].to;
            if(p[y].dep) continue;
            p[y].dep=p[u].dep+1;p[y].num=y;
            f[y]=u;
            q.push(y);
            if(p[y].dep<=2) vis[y]=1;
        }
    }
}

int main()
{
    n=read();
    for(int i=1;i<n;i++)
    {
        int u=read(),v=read();
        add(u,v);add(v,u);
    }
    bfs(1);
    sort(p+1,p+n+1,cmp);
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        if(vis[p[i].num])    continue;
        ans++;
        int u=f[p[i].num];
        vis[u]=1;
        for(int j=head[u];j;j=e[j].nxt) vis[e[j].to]=1;
    }
    printf("%d\n",ans);
    return 0;
}
/*
7
1 2
2 3
2 4
4 5
4 6
5 7

7
1 2
1 3
2 4
2 5
3 6
1 7

7
1 2
2 3
3 4
3 5
3 6
3 7
*/