主題
題目連結：
題目意譯：
你被給定一棵樹（即一個連通的、無向的圖，且其無環）其由編號為 0 到 n - 1 的 n 個節點且根節點為節點 0。該樹將以一個索引值從 0 開始且大小為 n 的陣列 parent 所表示，其中 parent[i] 為節點 i 的父母節點。由於節點 0 是根節點，因此 parent[0] == -1。
你同時也被給定一個長度為 n 的字串 s，其中 s[i] 為指派給節點 i 的字元。
回傳樹中最長路徑的長度，其中該路徑滿足在路徑上沒有相鄰兩個節點有著相同的字元。
限制：
n == parent.length == s.length
1 ≦ n ≦ 10 ^ 5
0 ≦ parent[i] ≦ n - 1 for all i ≧ 1
parent[0] == -1
parent 代表著一棵合法的樹。
s 只由小寫英文字母組成。
範例測資：
範例 1：
輸入： parent = [-1,0,0,1,1,2], s = "abacbe"
輸出： 3
解釋： 在樹中最長的路徑使得每兩個相鄰節點都是不同的字元為路徑：0 -> 1 -> 3。這個路徑的長度為 3，所以回傳 3。
可以證明沒有更長且滿足條件的路徑存在。
範例 2：
輸入： parent = [-1,0,0,0], s = "aabc"
輸出： 3
解釋： 在樹中最長的路徑使得每兩個相鄰節點都是不同的字元為路徑：2 -> 0 -> 3。這個路徑的長度為 3，所以回傳 3。
解題思維：
可以看到，假設我們知道答案是位於在以某個節點 i 作為根節點的子樹 Ti 中（所以給定的整棵樹可表為 T0），只是不知道實際上是哪一條路徑。則我們將答案的可能性分成以下三類：
一，答案實際上是位於 Ti 的某棵子樹 Tj 之中。
二，答案實際上是某棵子樹 Tj 中從節點 j 出發的一條路徑加上節點 i 的字元後所形成的。也可以看成是從節點 i 走到 Tj 的盡可能之「深處」（即往葉節點方向走）。
三，答案實際上是橫跨兩棵子樹 Tj 和 Tk 所形成的。可以看做是 Tj 中有一條從節點 j 往深處之盡可能長的路徑加上 Tk 中有一條從節點 k 往深處之盡可能長的路徑以及兩者之間的節點 i 所組成。
（注：這邊忽略了答案為長度 1 的情況，因為此狀況下任何節點本身都是答案，所以很簡單）
而我們知道答案一定在 T0 裡（畢竟這就是問題本身），只是我們不知道答案實際上是哪種情況。因此我們需要每一種都判斷一次才能知道。
所以對於種類一，這很單純，就是遞迴求解子樹而已。
對於種類二則我們需要知道從每一棵子樹從根節點最深可以往深處走到多深。而這本身也可以分解成子樹的子樹之子問題，也就是假設現在在 Tj 這棵樹中，並且我們已經知道了 Tj 所有子樹各自往深處可以走多深。則 Tj 可以往深處走多深可以直接根據這些子樹算出來，也就是節點 j 和這些子樹的路徑直接湊在一起看看看誰最長（當然，要記得篩選出合法的路徑）；如果都接不了，則 Tj 就只能走到節點 j 本身而已。
而對於種類三則和種類二類似，我們一樣需要知道每一棵可以往深處走多深。然後選出兩條可以用節點 i 接在一起的路徑。假設這兩條路徑是來自 Tj 和 Tk，則可以看到節點 i 的字元不能與節點 j 或節點 k 一樣。而為了最大化這個橫跨的長度，Tj 和 Tk 的路徑需要是所有子樹中最長的兩個。也因此實際上種類二可以直接合併到這邊，因為我們可以直接將接不上節點 i 的子樹之路徑視為長度 0。
總結來說：
我們需要把問題拆成若干個子樹遞迴去解（為了快速知道某個節點的子樹之根節點，我們需要先將給定的陣列 parent 轉成鄰接表（Adjacency List），見這題）。
而在過程中除了記錄最長合法路徑之長度以外，還需要記錄每一棵樹從根節點可以往深處走多深（計算方式如先前所述）以便計算回到上一層後「合併」各個子樹的答案。而這個合併後的答案也可能是最長的路徑，所以需要與「當前」的答案做比較取最大者。
最後整個過程結束後便可得到所求最長路徑。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
