思路：树形DP

定义$f[i]$表示从$i$点出发所能到达的节点数量，也就是最终输出的答案

我们首先需要去在以$i$为根的子树中找到节点编号最小的节点$u$

那么则有状态转移方程$f[i]=f[u]+1$

如果$i$是叶子结点，则$f[i]=1$

从根节点1出发，跑一遍DFS即可，一遍递归一遍处理

代码

C++

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7,N=1E5+10;
vector<int>g[N];
int n,m,f[N];
int dfs(int u,int fa){
    if(g[u].size()==1&&g[u][0]==fa){  //当前节点为叶子结点
        f[u]=1;
        return u;
    }
    int minpoint=1e9;
    for(int &x:g[u]){
        if(x==fa)continue;
        minpoint=min(minpoint,dfs(x,u));
    }
    f[u]=f[minpoint]+1;
    return min(u,minpoint);
}
int main(){
    cin>>n;
    for(int i=1;i<n;i++){
        int a,b;
        cin>>a>>b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    dfs(1,0);
    for(int i=1;i<=n;i++)cout<<f[i]<<" ";
    return 0;
}

Java

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

public class Main {
    static List<List<Integer>> graphs = new ArrayList<>();

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        for (int i = 0; i < n + 1; i++) {
            graphs.add(new ArrayList<>());
        }
        for (int i = 0; i < n - 1; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            graphs.get(u).add(v);
            graphs.get(v).add(u);
        }
        int[] min = new int[n + 1];
        Arrays.fill(min, Integer.MAX_VALUE);
        dfs(1, -1, min);
        int[] res = new int[n + 1];
        for (int i = 1; i < res.length; i++) {
            int k = 1;
            int v = i;
            while (min[v] != v) {
                v = min[v];
                k++;
            }
            res[i] = k;
        }
        for (int i = 1; i < res.length; i++) {
            System.out.print(res[i] + " ");
        }
    }

    private static void dfs(int cur, int p, int[] min) {
        for (int son : graphs.get(cur)) {
            if (son == p) {
                continue;
            }
            dfs(son, cur, min);
            if (min[cur] > Math.min(son, min[son])) {
                min[cur] = Math.min(son, min[son]);
            }
        }
        if (min[cur] == Integer.MAX_VALUE) {
            min[cur] = cur;
        }
    }

}

Python

n = int(input())
tree = [[] for _ in range(n+1)]
for _ in range(n-1):
    a, b = map(int, input().split())
    tree[a].append(b)
    tree[b].append(a)
tree[1].append(0) # 这里注意
nums = [0] * (n + 1)
def dfs(fa, cur):
    if len(tree[cur]) == 1:  # 到了根节点
        nums[cur] = 1
        return cur
    min_val = n + 1
    for son in tree[cur]:
        if son == fa: continue
        min_val = min(min_val, dfs(cur, son))
    nums[cur] = nums[min_val] + 1
    return min(cur, min_val)
dfs(0, 1)
print(" ".join([str(num) for num in nums[1:]]))

题目内容

小红最近沉迷上了PVZ，尤其喜欢自己设计一些关卡，而在设计关卡时，尤其偏爱传送门(进入门的一端后，会从另一端出现)。

这天，小红又设计了一个关卡，不同于PVZ的平面结构，这个关卡在一棵根节点为1的树上。

树上的每个节点都有一个脑子以及一个传送门，而玩家则是一个僵尸。每个传送门，会将玩家传送到该节点子树中除该节点外编号最小的节点处。

小红想知道，从任意一个节点出发，到叶节点为止，玩家一共能吃到多少脑子？

输入描述

一行一个整数$n$，表示树上的节点数量。

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

$1\le n\le10^5$

$1\le u,v\le n$

输出描述

输出一行，$n$个整数。第$i$个数表示从第$i$个节点出发，可以吃到的脑子数量是多少。

样例

输入

4
1 3
3 2
4 1

输出

2 1 2 1