一道编程题，用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.用递归逆序输出字符
2023年12月 GESP等级认证C++编程（三级）试题解析
2024-06-18 09:38

编程小伙伴测评网的博客 2023年12月 GESP等级认证C++编程（三级）试题解析
没有解决我的问题, 去提问

悬赏问题

¥15 metadata提取的PDF元数据，如何转换为一个Excel
¥15 关于arduino编程toCharArray()函数的使用
¥100 vc++混合CEF采用CLR方式编译报错
¥15 coze 的插件输入飞书多维表格 app_token 后一直显示错误，如何解决？
¥15 vite+vue3+plyr播放本地public文件夹下视频无法加载
¥15 c#逐行读取txt文本，但是每一行里面数据之间空格数量不同
¥50 如何openEuler 22.03上安装配置drbd
¥20 ING91680C BLE5.3 芯片怎么实现串口收发数据
¥15 无线连接树莓派，无法执行update，如何解决？（相关搜索：软件下载）
¥15 Windows11, backspace, enter, space键失灵

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

2条回答 默认 最新

悬赏问题

2条回答默认最新