给出一棵树，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