题目

Q3：小红有一棵传送树，树上有 n 个节点，编号为 1 到 n ，其中 1 号节点为根节点。

每个节点都有一个传送门，传送门只可以将小红传送到子树中除了自己的其他节点中编号最小的节点。

小红想知道，经过若干次传送门直到叶子节点为止，可以到达的节点数量是多少。

输入描述：
一行一个整数n，表示树上的节点数量。
接下来n - 1行，每行两个整数u, v，表示u号节点和v号节点之间有一条边。
1 < n < 10^5
1 < u, v < n

输出描述：
输出一行，n个整数，分别对树上n个节点计算答案。

解答

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<vector<int>> edge;
vector<int> nxt;
int n;

/**
 * @brief DFS the tree from root and update the nxt array to record the node it will reach.
 * @param root: cur node
 * @param from: parent of root
 */
void findNext(int root, int from) {
  for (int v : edge[root]) {
    if (v == from) {
      continue;
    }
    findNext(v, root);
    if (nxt[root] == -1 || nxt[root] > min(v, nxt[v])) {
      nxt[root] = min(v, nxt[v]);
    }
  }
  
  // leaf node
  if (nxt[root] == -1) {
    nxt[root] = root;
  }
}

int get(int u) {
  int cnt = 0;
  while (nxt[u] != u) {
    cnt++;
    u = nxt[u];
  }
  
  return cnt;
}

int main() {
  cin >> n;
  edge.resize(n + 1);
  nxt.resize(n + 1);
  for (int i = 1; i <= n; ++i) {
    int a, b;
    cin >> a >> b;
    edge[a].push_back(b);
    edge[b].push_back(a);
  }
  
  findNext(1, 0);
  
  for (int i = 1; i <= n; ++i) {
    cout << get(i);
    if (i != n) {
      cout << ' ';
    } else {
      cout << endl;
    }
  }
}