在线编程介绍
阿里云开发者社区在线编程产品，针对广大开发者学习、实践、面试、应聘、考试认证等打造的免费在线刷题神器。题库来自笔试模拟题、算法大赛模拟题等，界面整洁明了，操作简单，为用户营造专心答题的学习环境。点击链接开始体验：https://developer.aliyun.com/coding
题目描述
等级：困难
知识点：深度优先搜索/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
输入：
3
[1,1]
[1,2,2]
输出：
3
解题思路：DFS
如果我们删除了一条边，那么一定将其分成了两棵树，其中一棵树一定为原树的子树，那么我们就可以利用DFS序将树遍历一遍得出每个点的时间戳。
DFS序即为每个点的在一次DFS中的遍历顺序，从定义可以知道，子树上的每个节点的DFS序一定连续，因此我们可以求出每棵子树所对应的区间，剩下的节点即为另一棵树。
此时我们就可以利用树状数组求每个区间里面不同的数的个数，由于一个子树区间可能会在数组中间，会将剩下的数字分为左右两部分，因此我们需要将原权值数组扩充一倍，然后进行计算。
需要注意的是，现在这个权值数组不是输入的权值数组，而是根据DFS序进行重新排序的数组。
是不是有思路了呢，点击链接立刻答题：>>查看题目：118.树的拆分