题目

题目描述：
给出一颗n个点n−1条边的树，点的编号为1,2,...,n−1,n，对于每个点 i (1<=i<=n)，输出与点i距离为2的点的个数。
两个点的距离定义为两个点最短路径上的边的条数。

输入描述：
第一行一个正整数n。
接下来n−1行每行两个正整数{ui,vi}表示点{ui,vi}之间有一条边。

输出描述：
输入共n行，第{i}i行输出一个整数表示与点i距离为2的点的个数。

解析

这道题看到这道题，我脑子里就闪过一个念头：简单！给他T了！
  • 讲道理如果这道题不考虑时间复杂度的话我就直接循环bfs想给他过了QAQ（况且这道题我还看成了图）。

那我们下面讲咱这道题是怎么写的（基于这道题是树，图的话也行，加个visited记录就好了）：
  1. 这道题简单来说，就是要我们数点，但是我们想到，我们数1的点会数，但数2的点不会啊。
  2. 想到这里你就已经成功了一大半：但其实，我们只要会数1的点，我们就可以数出任意长的点。
  3. 为什么这么说呢？因为距离为2的点就是距离为1的点的距离为1的点对吧，同理距离为3的点就是距离为1的点的距离为1的点的距离为1的点对吧，同理距离（禁止套娃）。
  4. 所以我们这道题只要知道，这个点距离为1的点，有几个距离为1的点，就可以得出当前这个点距离为2的点的数量了！
  5. ————————————————————skr————————————————————
  6. 如果你在看，我知道你八成被我绕晕了哈哈哈哈。下面简单来说：
  7. 某一点距离为2的点数就是：与该点（要计算的那点）相邻的点（距离1的点），这些点所相邻的点的数量（距离2的点数）。
  8. 栗子：假如某点有三个直接子节点，这些直接子节点的直接子节点数分别为1，2，3。我们就知道这个点距离为2的点有3个了。
  9. 同理，距离n的节点数就是，要计算点的直接子节点数，这些节点数的距离n-1的节点数-1之和了（为啥要减一？）因为在存储中，父节点也是子节点。

算法操作：
  1. 所以我们这里的方法应该就是：
  2. 先dfs遍历求每一个位置上距离为1的数组。
  3. 再dfs一遍求统计求和每一个位置上距离为2的数组。

打代码咯：
  1. 还是用我们熟悉的前向星存储。
  2. 然后就是两边bfs啦。
  3. 最后按顺序输出就好了。
  4. 看我代码咯~

AC代码 

#include <iostream>
#include <cstring>
using namespace std;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//代码预处理区

const int MAX = 2e5 + 7;
int head[MAX], tot;
struct EDGE {
    int v, next;
} edge[MAX << 1];
int n, num[MAX], ans[MAX];
//全局变量区

void init();
void add_edge(int u, int v);
void dfs(int u, int fa);
void calc(int u, int fa);
//函数预定义区

int main() { 
    IOS;
    // freopen("in.txt", "r", stdin);
    cin >> n;
    init();
    for (int i = 1; i <= n - 1; i++) {
        int u, v; cin >> u >> v;
        add_edge(u, v);
        add_edge(v, u);
    }
    memset(num, 0, sizeof num); dfs(1, 0);
    memset(ans, 0, sizeof ans); calc(1, 0);
    for (int i = 1; i <= n; i++)
        cout << ans[i] << endl;
    return 0; 
}
void init() {
    memset(head, 0, sizeof head); tot = 0;
}
void add_edge(int u, int v) {
    tot++;
    edge[tot].v = v;
    edge[tot].next = head[u];
    head[u] = tot;
}
void dfs(int u, int fa) {
    int cnt = 0;
    for (int i = head[u]; i; i = edge[i].next) {
        int v = edge[i].v;
        cnt++;
        if (v == fa) continue;
        dfs(v, u);
    }
    num[u] = cnt;
}
void calc(int u, int fa) {
    int cnt = 0;
    for (int i = head[u]; i; i = edge[i].next) {
        int v = edge[i].v;
        cnt += num[v] - 1;
        if (v == fa) continue;
        calc(v, u);
    }
    ans[u] = cnt;
}
//函数区