算法笔试模拟题精解之“树的拆分” <117算法笔试模拟题精解之“树的拆分”贡献者 | 猿圈简介：如果我们删除了一条边，那么一定将其分成了两棵树，其中一棵树一定为原树的子树，那么我们就可以利用 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输入：3118>算法笔试模拟题精解之“树的拆分”[1,1][1,2,2]输出：3解题思路：DFS如果我们删除了一条边，那么一定将其分成了两棵树，其中一棵树一定为原树的子树，那么我们就可以