网络铺设

问题描述

你现在是城市的主人
现在有 $n$ 个村庄，已经修建了 $n-1$ 条道路，使得各个村庄作为节点，路作为边，构成一棵树。
假设第 $a$ 个村庄到第 $b$ 个村庄有路相连，则从 $a$ 走到 $b$ 或者从 $b$ 走到 $a$ 需要走 $1\text{m}$ 。

你需要输出 $n$ 个数，第 $i$ 个数代表从第 $i$ 个村庄出发，距离他最远的村庄的距离

输入格式

第一行一个整数 $n$ , $0\le n\le10^5$
接下来有 $n-1$ 行，每行 $a,b$ 代表第 $a$ 个村庄，到第 $b$ 个村庄有一条路。
$1\le a,b\le 10^5$

保证输入结构是一棵树

输出格式

输出一行 $n$ 个数，表示答案

样例输入

5
5 1
1 2
2 3
3 4

样例输出

3 2 3 4 4

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

struct edge {
    int u, v, next; /*一条边的起始点、终止点、下一条边的编号*/
} e[200005];

int tot = 0/*边的总数*/, n, a, b, maxLen = 0, fromV1[100005], fromV2[100005], temp[100005];
vector<int> head(100005, -1);
bool vis[100005];  // 记得每次dfs后都用memset(vis,0,sizeof(vis))

void addEdge(int u, int v) {
    e[tot].u = u, e[tot].v = v, e[tot].next = head[u], head[u] = tot++;
}

void dfs(int u, int len, int& v1, int ans[]) {
    if (maxLen < len)
        v1 = u, maxLen = len;
    ans[u] = len;
    for (int i = head[u]; i != -1; i = e[i].next)
        if (!vis[e[i].v])
            vis[e[i].v] = true, dfs(e[i].v, len + 1, v1, ans);
}

/*
直径的端点通过以下步骤获得：
1.从任意一点出发到达该点的最远点x
2.从x出发到达x的最远点y
3.x和y就是直径的端点

从上述的<1>中可知，对于树上任意一点，它的最远点必定是直径的两个端点之一
*/

int main() {
    cin >> n;
    for (int i = 1; i < n; ++i)
        scanf("%d%d", &a, &b), addEdge(a, b), addEdge(b, a);
    int v1 = 0, v2 = 0, t = 0;  // 这里求出的v1、v2就是树的直径的两个端点。
    dfs(1, 0, v1, temp);
    maxLen = 0;
    memset(vis, 0, sizeof(vis));
    dfs(v1, 0, v2, fromV1);
    memset(vis, 0, sizeof(vis));
    dfs(v2, 0, t, fromV2);
    for (int i = 1; i <= n; ++i)
        printf("%d ", max(fromV1[i], fromV2[i]));
    return 0;
}