← 返回目录

算法笔试模拟题精解之“树的拆分”

第 45 / 74 卷日期：

算法笔试模拟题精解之“树的拆分”

贡献者 | 猿圈

简介：如果我们删除了一条边，那么一定将其分成了两棵树，其中一棵树一定为

原树的子树，那么我们就可以利用 DFS 序将树遍历一遍得出每个点的时间戳。

题目描述

等级：困难

知识点：深度优先搜索 /DFS、树状数组

查看题目：树的拆分

给你一个有 n 个节点的树 , 节点标号 1-n。每个节点有一个权值 w[i]，一棵树的

价值为树上所有不同的权值的数量。

现在你可以删除一条边，问删除一条边后形成的两棵新树的价值之和最大为多少。

第一行输入一个 n，表示一共有 n 个节点（1 <= n <= 10^5）。

第二行输入 n-1 个数，表示第 i+1 个节点和第 e[i] 个节点有一条边相连（1 <=

e[i] < i+1）

第三行输入 n 个数，第 i 个数表示第 i 个节点的权值 wi。

输出一个数字，表示删除一条边后两棵树最大的价值和

示例 1

输入：

[1,1]

[1,2,2]

输出：

3

解题思路：DFS

如果我们删除了一条边，那么一定将其分成了两棵树，其中一棵树一定为原树的

子树，那么我们就可以利用 DFS 序将树遍历一遍得出每个点的时间戳。

DFS 序即为每个点的在一次 DFS 中的遍历顺序，从定义可以知道，子树上的每

个节点的 DFS 序一定连续，因此我们可以求出每棵子树所对应的区间，剩下的节点

即为另一棵树。

此时我们就可以利用树状数组求每个区间里面不同的数的个数，由于一个子树区

间可能会在数组中间，会将剩下的数字分为左右两部分，因此我们需要将原权值数组

扩充一倍，然后进行计算。

需要注意的是，现在这个权值数组不是输入的权值数组，而是根据 DFS 序进行

重新排序的数组。

是不是有思路了呢，点击链接立刻答题：>>118. 树的拆分

全站分卷索引 · 74 卷
  1. 1一、算法思想
  2. 2算法笔试模拟题精解之“打怪兽”
  3. 31.2 贪心
  4. 4算法笔试模拟题精解之“最强的团队”
  5. 5算法笔试模拟题精解之“Tom 爱吃巧克力”
  6. 6算法笔试模拟题精解之“吃奶酪”
  7. 7算法笔试模拟题精解之“一的个数”
  8. 8算法笔试模拟题精解之“Bob 的花束”
  9. 9算法笔试模拟题精解之“钱庄”
  10. 10算法笔试模拟题精解之“移动射击”
  11. 11算法笔试模拟题精解之“相似数组”
  12. 12算法笔试模拟题精解之“过吊桥”
  13. 13算法笔试模拟题精解之“完美排列”
  14. 14算法笔试模拟题精解之“采摘圣诞果”
  15. 15算法比赛模拟题精解之“Tairitsu and Dynamic Objects”
  16. 16算法笔试模拟题精解之“Codancer 的炸弹引爆”
  17. 17算法笔试模拟题精解之“学习小组”
  18. 18算法笔试模拟题精解之“恢复字符串”
  19. 191.3 DP/ 动态规划
  20. 20算法笔试模拟题精解之“寻找等比数列”
  21. 21算法笔试模拟题精解之“字符配对”
  22. 22算法笔试模拟题精解之“数组染色”
  23. 23算法笔试模拟题精解之“连绵的群山”
  24. 24算法笔试模拟题精解之“难住Tom 的问题”
  25. 25算法笔试模拟题精解之“变化的字符”
  26. 26算法笔试模拟题精解之“跳房子”
  27. 27算法笔试模拟题精解之“寒假活动”
  28. 28算法笔试模拟题精解之“最短路”
  29. 29算法笔试模拟题精解之“codancer 上楼”
  30. 30算法笔试模拟题精解之“木棒拼接”
  31. 31算法笔试模拟题精解之“Codancer 的数组封印”
  32. 32算法笔试模拟题精解之“Jerry 的异或运算”
  33. 33算法笔试模拟题精解之“小明的数学作业”
  34. 34算法笔试模拟题精解之“奇偶数列”
  35. 351.4 剪枝
  36. 361.5 尺取法
  37. 37算法笔试模拟题精解之“调整数组”
  38. 38算法笔试模拟题精解之“最优分组”
  39. 39算法笔试模拟题精解之“破译密码”
  40. 40二、数据结构
  41. 412.2 搜索
  42. 42算法笔试模拟题精解之“能量半径”
  43. 43算法笔试模拟题精解之“苹果收获程序”
  44. 44算法笔试模拟题精解之“恐怖的辐射”
  45. 45算法笔试模拟题精解之“树的拆分”
  46. 46算法笔试模拟题精解之“Password”
  47. 47算法笔试模拟题精解之“神奇数字在哪里”
  48. 48算法笔试模拟题精解之“神奇的棋子”
  49. 492.3 树
  50. 50算法笔试模拟题精解之“Codancer 的旅行”
  51. 51算法笔试模拟题精解之“Codancer 的求和”
  52. 52算法笔试模拟题精解之“找出二叉搜索树的第2 大的数”
  53. 532.4 线型
  54. 54算法笔试模拟题精解之“最活跃的数”
  55. 55算法笔试模拟题精解之“非递减序列”
  56. 56算法笔试模拟题精解之“Tom 跳方格”
  57. 57算法笔试模拟题精解之“复杂的字符串”
  58. 58算法笔试模拟题精解之“神秘消失”
  59. 59三、计算
  60. 60算法笔试模拟题精解之“简单题？
  61. 61算法笔试模拟题精解之“朋友一生一起走”
  62. 62算法笔试模拟题精解之“正三角塔”
  63. 63算法笔试模拟题精解之“组队难题”
  64. 64算法笔试模拟题精解之“2n 合体”
  65. 65算法笔试模拟题精解之“平行线”
  66. 66算法笔试模拟题精解之“叠叠高”
  67. 67算法笔试模拟题精解之“公平”
  68. 68算法笔试模拟题精解之“Tom 的手工课”
  69. 69算法笔试模拟题精解之“填数问题”
  70. 70算法笔试模拟题精解之“Jerry 的考验”
  71. 71算法笔试模拟题精解之“超车”
  72. 72算法笔试模拟题精解之“坏掉的时钟”
  73. 73算法笔试模拟题精解之“期末考试”
  74. 74算法笔试模拟题精解之“滑雪比赛”