算法筆試模拟題精解之“樹的拆分”

線上程式設計介紹

阿裡雲開發者社群線上程式設計産品，針對廣大開發者學習、實踐、面試、應聘、考試認證等打造的免費線上刷題神器。題庫來自筆試模拟題、算法大賽模拟題等，界面整潔明了，操作簡單，為使用者營造專心答題的學習環境。點選連結開始體驗：

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]

輸出：

解題思路：DFS

如果我們删除了一條邊，那麼一定将其分成了兩棵樹，其中一棵樹一定為原樹的子樹，那麼我們就可以利用DFS序将樹周遊一遍得出每個點的時間戳。

DFS序即為每個點的在一次DFS中的周遊順序，從定義可以知道，子樹上的每個節點的DFS序一定連續，是以我們可以求出每棵子樹所對應的區間，剩下的節點即為另一棵樹。

此時我們就可以利用樹狀數組求每個區間裡面不同的數的個數，由于一個子樹區間可能會在數組中間，會将剩下的數字分為左右兩部分，是以我們需要将原權值數組擴充一倍，然後進行計算。

需要注意的是，現在這個權值數組不是輸入的權值數組，而是根據DFS序進行重新排序的數組。

是不是有思路了呢，點選連結立刻答題：>>

檢視題目：118.樹的拆分 另有線上程式設計3月份比賽正式開啟！機械鍵盤等你拿！