首页 > 试题广场 >

我们的距离

[编程题]我们的距离

热度指数：238 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

牛妹给牛牛出了一道题，牛牛需要通过这道题才能见到牛妹。

现在有一棵树，每条边的长度为 $1$ ，定义 $dis(i, j)$ 为结点 $i, j$ 之间的距离，定义结点 $i$ 的权值为 $f(i) = \sum_{1\leq k\leq n \&\& k \neq i}dis(i, k)$ ，现在求 $1$ 到 $n$ 所有点的权值。

返回 $n$ 个整数，分别为 $f(1), f(2), \dots f(n)$

示例1

输入

5,[(2,5),(5,3),(5,4),(5,1)]

输出

[7,7,7,7,4]

备注:

第一个参数为整数  。
第二个参数为大小为 n-1n−1 的点对 (u_i, v_i)(ui,vi) 的集合 EdgeEdge ，其中 (u_i, v_i)(ui,vi) 表示结点 u_iui 与结点 v_ivi 之间有一条边，1leq u_i, v_i leq n1≤ui,vi≤n

算法知识视频讲解

星云·忒弥斯

发表于 2021-08-16 13:37:39

const int M = 1e5+7; class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * 展开全文

AimerAimer

发表于 2021-10-13 20:58:47

题意：给定一棵树，遍历树的每一个节点，都返回一个值，这个值是该节点到其他节点的边长之和。方法一：暴力dfs（超时）思路： &nbs 展开全文

摸鱼学大师

发表于 2021-08-08 17:28:45

思路：题目的主要信息：一棵树每边长度为1，节点到节点的距离为某个节点的权值现求树每个节点的权值方法一：两次dfs具体做法：我们可以用两次dfs解决这个问题。第一次dfs遍历这棵树，找到每个节点有多少个子节点，第二次dfs遍历每个节点，根据第一次找到的子节点数推算出到其他任何节点的距离。展开全文

martin0621

发表于 2021-08-25 18:08:18

方法零：用边的信息构造邻接矩阵，用floyd算法求节点间的最短距离，求和输出。这个方法用python实现超时，floyd算法对于边相对稀疏的树效率不高。（C++这么做可以通过，代码略）方法一：遍历所有边，更新连通分量（Connected Component）和每个连通分量内的节点两两之间距离，最后求展开全文