一道编程题，用c++编程，求助

给定一颗无根树，假设它有n个节点，节点编号从1到n，求任意两点之间的距离之和，也就是求任意一点到其它点的距离之和，边长都为1。要求时间复杂度为O(n)

写回答
好问题 0 提建议
追加酬金
关注问题
分享
邀请回答
编辑收藏删除结题
收藏举报

2条回答默认最新

关注

码龄粉丝数原力等级 --

被采纳

被点赞

采纳率
ZSGG_ACM 2016-05-23 04:31
关注
先做一遍DFS求出所有节点到根节点的距离之和，然后可以发现，如果知道到一个点的距离之和，可以用O(1)求出所有节点到它相邻点的距离之和

本回答被题主选为最佳回答 , 对您是否有帮助呢?

解决无用
评论打赏
分享
举报

评论

按下Enter换行，Ctrl+Enter发表内容

查看更多回答(1条)

报告相同问题？

关注问题

有关c＋＋的一道编程题 c++
2021-08-22 16:43

回答 4 已采纳如果一个数是素数,那么除了1和它本身外没有数字能整除他判断i是否为素数:从头开始判断,如果a[i]为合数,将a[i]置0对于a[k],判断其是否为素数,只需要判断他是否会被小于a[k]的素数整除即可(
一道编程题，用c++编程，求助
2016-05-23 04:19

回答 2 已采纳先做一遍DFS求出所有节点到根节点的距离之和，然后可以发现，如果知道到一个点的距离之和，可以用O(1)求出所有节点到它相邻点的距离之和
请问一道c++的编程题 c++
2021-08-19 19:21

回答 1 已采纳 #include<iostream> #include<algorithm> using namespace std; int main(){ int n,maxn=
c语言编程题进制转换,[求助]进制转换的编程题
2021-05-22 08:03

探索者19的博客 #include #include #define ElemType int #define MAXNUM 50 typedef struct {ElemType stack[MAXNUM]; int top; }Qstack; void InitStack(Qstack *p) {if(!... } } 这个是用C来写的,上面那个是用C++的知识来写的.
C++求救，一道编程题不知道怎么做 c++
2019-06-19 20:45

回答 1 已采纳 # 如果问题解决，请点下我回答左上角的采纳 ``` #include #include int checkpwd(char * pwd) { int n = strlen(pwd)
动态规划c++编程题：铺砖 c++
2021-08-21 18:14

回答 4 已采纳理解图
求解一道编程题，马的智障 c++ c语言
2016-08-30 15:30

回答 6 已采纳思路就是递归， 1，先判断大小，由于从n到K和从K到N是一样的时间，(假设Nk/2 3.n>K/2的情况下又分为两点，(n-(n-k/2))*2 或者是 k-n 两种时间比较哪种更优，如果
求助c语言一道题解法
2022-12-26 22:32

yaobao666的博客求助解答
c++语言编程题，求解 c++ 有问必答
2021-10-14 16:10

回答 4 已采纳 #include <stdio.h> int main() { int n; scanf("%d",&n); printf("%d",(n+1)%7+1);
严格的第k小c++编程题 c++
2021-08-20 19:16

回答 1 已采纳 #include<bits/stdc++.h> using namespace std; int a[100010]; int main() { int n,k; cin
C++基础编程习题关于矩阵然后排序 c++ 有问必答
2021-08-06 21:15

回答 1 已采纳可以先排序，再把前4个元素和最后一个元素移动到指定位置 #include <stdio.h> #define N 5 void swap(int *a,int *b) { int
C++ Primer Plus教材编程题提问
2023-05-26 19:43

TommieBao的博客求助大神，第6章编程题第7题，我的辅音字母个数为什么不统计？
【C++编程题】错误的里程表
2021-09-19 00:09

通心粉丝的博客现在，小明向你求助：根据里程表显示的数字，给出真实的行驶里程。【输入形式】输入有多组测试数据。输入第一行正整数T，表示有多少组测试数据。后面有T行，每行一个非负整数，表示里程表显示数字，里面不...
几道基础的C++编程题2
2022-03-13 22:39

什么时候上岸？的博客 1.输入三边长度求面积 2.逆序输出 3.用递归逆序输出字符
(编程题）说反话，求助
2022-03-11 13:24

翼空丶的博客看了好几遍不知道问题出在哪 #include<iostream> #include<cstring> using namespace std; int main() { char str[80]; int len; cin.getline(str,81); len = strlen(str);... ...
没有解决我的问题, 去提问

悬赏问题

¥15 socket通信实现多人聊天室疑惑
¥15 DEV-C++编译缺失
¥33 找熟练码农写段Pyhthon程序
¥100 怎么让数据库字段自动更新
¥15 antv g6 力导向图布局
¥15 quartz框架，No record found for selection of Trigger with key
¥15 锅炉建模+优化算法，遗传算法优化锅炉燃烧模型，ls-svm会搞，后面的智能算法不会
¥20 MATLAB多目标优化问题求解
¥15 windows2003服务器按你VPN教程设置后，本地win10如何连接？
¥15 求一阶微分方程的幂级数

一道编程题，用c++编程，求助

2条回答 默认 最新

悬赏问题

2条回答默认最新