普通网友 2016-05-23 04:19 采纳率: 50%
浏览 1359
已采纳

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

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

  • 写回答

2条回答 默认 最新

  • ZSGG_ACM 2016-05-23 04:31
    关注

    先做一遍DFS求出所有节点到根节点的距离之和,然后可以发现,如果知道到一个点的距离之和,可以用O(1)求出所有节点到它相邻点的距离之和

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论
查看更多回答(1条)

报告相同问题?

悬赏问题

  • ¥50 hyper默认的default switch
  • ¥15 网站打不开,提示502 Bad Gateway
  • ¥20 基于MATLAB的绝热压缩空气储能系统代码咨询
  • ¥15 R语言建立随机森林模型出现的问题
  • ¥20 unity内置语言切换的按钮设置
  • ¥15 中级微观经济学,生产可能性边界问题
  • ¥15 TCP传输时不同网卡传输用时差异过大
  • ¥15 请各位看看我写的属于什么算法,或者有更正确的写法?
  • ¥15 html5 qrcode 扫描器
  • ¥15 爬取网页信息并保存需要完整代码