思路：DFS

以 $1$ 号点为根，求出从 $1$ 号点到所有点的距离，如果距离小于等于 $k$ ，则将这个点加入到答案中。

此外，对于一个叶子节点，如果其距离 $d$ 小于 $k$ ，则说明还可以在这个叶子下添加 $k - d$ 个点，这些点成一条链。

所以，在进行以 $1$ 号点为根的树的遍历的过程中，即可获得从 $1$ 号点到每个点的距离，同时进行判断和答案计算即可。

时间复杂度：$O(n)$

代码

C++

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k;
    cin >> n >> k;   

    // 建图
    vector<vector<int>> g(n);
    for (int i = 1; i < n; ++i) {
        int u, v;
        cin >> u >> v;
        u--; v--;
        g[u].emplace_back(v);
        g[v].emplace_back(u);
    }

    const int INF = 0x3f3f3f3f;

    long long ans = 0;
    vector<int> dist(n, INF);
    // 计算1号点到每个点的距离，1号点到自己的距离为 0
    dist[0] = 0;
    function<void(int,int)> dfs = [&](int u, int fa) {
        // 如果1号点到u+1点的距离 <= k，则答案加1
        if (dist[u] <= k) {
            ans += 1;
        }

        // 如果1号点到叶子的距离 < k，则还可以再这个叶子下加 k - dist[u] 个
        if (u != 0 && g[u].size() == 1 && dist[u] < k) {
            ans += k - dist[u];
        }

        // 继续遍历子树 v 
        for (int v: g[u]) {
            if (v == fa) continue;
            dist[v] = dist[u] + 1;
            dfs(v, u);
        }
    };
    
    dfs(0, -1);

    cout << ans << "\n";

    return 0;
}

python

def dfs(u, fa):
    global ans
    # 如果1号点到u+1点的距离 <= k，则答案加1
    if dist[u] <= k:
        ans += 1
    # 如果1号点到叶子的距离 < k，则还可以再这个叶子下加 k - dist[u] 个
    if u != 0 and len(g[u]) == 1 and dist[u] < k:
        ans += k - dist[u]
    # 继续遍历子树 v 
    for v in g[u]:
        if v == fa:
            continue
        dist[v] = dist[u] + 1
        dfs(v, u)


n, k = map(int, input().split())

# 建图
g = [[] for _ in range(n)]
for _ in range(1, n):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    g[u].append(v)
    g[v].append(u)

INF = int(1e9)

ans = 0
dist = [INF] * n
# 计算1号点到每个点的距离，1号点到自己的距离为 0
dist[0] = 0

dfs(0, -1)

print(ans)

Java

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    static List<List<Integer>> g;
    static int[] dist;
    static int n, k;
    static long ans;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        k = scanner.nextInt();
        
        // 建图
        g = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            g.add(new ArrayList<>());
        }

        for (int i = 1; i < n; i++) {
            int u = scanner.nextInt() - 1;
            int v = scanner.nextInt() - 1;
            g.get(u).add(v);
            g.get(v).add(u);
        }

        final int INF = 0x3f3f3f3f;

        ans = 0;
        dist = new int[n];
        for (int i = 0; i < n; i++) {
            dist[i] = INF;
        }
        // 计算1号点到每个点的距离，1号点到自己的距离为 0
        dist[0] = 0;

        dfs(0, -1);

        System.out.println(ans);
    }

    static void dfs(int u, int fa) {
        // 如果1号点到u+1点的距离 <= k，则答案加1
        if (dist[u] <= k) {
            ans++;
        }
        // 如果1号点到叶子的距离 < k，则还可以再这个叶子下加 k - dist[u] 个
        if (u != 0 && g.get(u).size() == 1 && dist[u] < k) {
            ans += k - dist[u];
        }
        // 继续遍历子树 v 
        for (int v : g.get(u)) {
            if (v == fa) {
                continue;
            }
            dist[v] = dist[u] + 1;
            dfs(v, u);
        }
    }
}

题目内容

米小游有一个 $n$ 个节点的树，树根编号为 $1$ 。

米小游可以在叶子节点上添加一个新的儿子节点，添加后，添加的节点变成了新的叶子节点。

若干次操作后，米小游想问你距离树根不超过 $k$ 的节点最多可以有多少个。

输入描述

第一行，一个正整数$n$ 表示树中节点个数，$k$ 表示不超过树根的距离，

接下来 $n-1$ 行，每行输入两个整数 $u$ 和 $v$ ，表示节点 $u$ 和 $v$ 之间有一条边。

$1 \leq n \leq 10^5, 1\leq k\leq 10^9, 1\leq u,v\leq n$

输出描述

一个整数，表示若干次操作后距离树根不超过 $k$ 的节点最大数量。

样例

输入

4 2
1 2
1 3
1 4

输出

7

说明

若干次操作后，最终的树如下，此时有 $7$ 个点距离 $1$ 号点的距离小于等于 $2$

        1
      / | \
     2  3  4

       ↓↓↓

        1
      / | \
     2  3  4
    /   |   \
   5    6    7