遇到一个树的拆分问题，求解答。
给你一个有 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
条回答
写回答
写回答
-
如果我们删除了一条边，那么一定将其分成了两棵树，其中一棵树一定为原树的子树，那么我们就可以利用 DFS 序将树遍历一遍得出每个点的时间戳。DFS 序即为每个点的在一次 DFS 中的遍历顺序，从定义可以知道，子树上的每个节点的 DFS 序一定连续，因此我们可以求出每棵子树所对应的区间，剩下的节点即为另一棵树。此时我们就可以利用树状数组求每个区间里面不同的数的个数，由于一个子树区间可能会在数组中间，会将剩下的数字分为左右两部分，因此我们需要将原权值数组扩充一倍，然后进行计算。需要注意的是，现在这个权值数组不是输入的权值数组，而是根据 DFS 序进行重新排序的数组。 因此输入：3 [1,1] [1,2,2] 输出：3
2021-12-23 18:48:37赞同 展开评论 打赏
版权声明：本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
相关问答
问答排行榜
最热
最新
推荐问答
