給出一棵樹，parent[i]代表節點i的父節點ID，以及一個字符串s，s[i]代表每個節點的字符值，求樹中最長的一條滿足相鄰節點字符值不同的path的長度，DFS
先用dict建樹，保存與每個節點i相連的節點，然后DFS到每個節點處時，若為葉子結點，返回1，否則搜索該節點所有子節點，找出每個子樹i中符合要求的path長度l[i]，如果子節點和當前節點字符值不一樣，那么以當前節點為根，經過子樹i最多可以取長度為max(l[1:i-1]) + l[i] + 1，DFS每一層返回值為max(l)
1 #2246
2 #Runtime: 1720 ms (Beats 70.91%)
3 #Memory: 139.6 MB (Beats 72.12%)
4
5 class Solution(object):
6 def longestPath(self, parent, s):
7 """
8 :type parent: List[int]
9 :type s: str
10 :rtype: int
11 """
12 p = defaultdict(list)
13 for i in range(1, len(parent)):
14 p[parent[i]].append(i)
15 self.ans = 1
16
17 def DFS(r):
18 if not p[r]:
19 return 1
20 t = 1
21 for i in p[r]:
22 l = DFS(i)
23 if s[r] != s[i]:
24 self.ans = max(l + t, self.ans)
25 t = max(t, l + 1)
26 return t
27
28 DFS(0)
29 return self.ans