2246.Longest Path With Different Adjacent Characters
===

###### tags: `Hard`,`Tree`,`DFS`,`Array`,`String`,`Graph`,`Topological Sort`

[2246. Longest Path With Different Adjacent Characters](https://leetcode.com/problems/longest-path-with-different-adjacent-characters/)

### 題目描述

You are given a **tree** (i.e. a connected, undirected graph that has no cycles) **rooted** at node `0` consisting of `n` nodes numbered from `0` to `n - 1`. The tree is represented by a **0-indexed** array `parent` of size `n`, where `parent[i]` is the parent of node `i`. Since node `0` is the root, `parent[0]` == -1.

You are also given a string `s` of length `n`, where `s[i]` is the character assigned to node `i`.

Return *the length of the **longest path** in the tree such that no pair of **adjacent** nodes on the path have the same character assigned to them*.

### 範例

**Example 1:**


Input: parent = [-1,0,0,1,1,2], s = "abacbe"
Output: 3
Explanation: The longest path where each two adjacent nodes have different characters in the tree is the path: 0 -> 1 -> 3. The length of this path is 3, so 3 is returned.
It can be proven that there is no longer path that satisfies the conditions. 

**Example 2:**


Input: parent = [-1,0,0,0], s = "aabc"
Output: 3
Explanation: The longest path where each two adjacent nodes have different characters is the path: 2 -> 0 -> 3. The length of this path is 3, so 3 is returned.

**Constraints**:

* `n` == `parent.length` == `s.length`
* 1 <= `n` <= 10^5^
* 0 <= `parent[i]` <= `n` - 1 for all `i` >= 1
* `parent[0]` == -1
* `parent` represents a valid tree.
* `s` consists of only lowercase English letters.

### 解答

class Solution:
    def longestPath(self, parent: List[int], s: str) -> int:
        def dfs(node):
            #print('#',node)
            subtree_stats = []

            ans = 1
            max2 = [0,0]
            for child in self.edge[node]:
                if self.visited[child] == 1:
                    continue
                self.visited[child] = 1
                _ans = dfs(child)

                if s[child] != s[node]:
                    if _ans > max2[0]:
                        #print('update1')
                        max2 = [_ans, max2[0]]
                    elif _ans > max2[1]:
                        max2[1] = _ans
                #print(node,child, _ans , max2)

            
            ans = sum(max2) + 1
            #print(node, max2, ans)

            self.ans[node] = ans
            #print('#',node)
            return max2[0]+1
        

        n = len(s)
        self.ans = [ 0 for _ in range(n)]
        self.edge = dict()
        for i in range(n):
            self.edge[i] = []
        for i, p in enumerate(parent):
            if i == 0:
                continue
            self.edge[p].append(i)

        self.visited = [ 0 for _ in range(n)]
        self.visited[0]= 1

        root_stat = dfs(0)

        return max(self.ans)

> [name=玉山]

提供一筆測資
S.longestPath([-1,0,0,1,1,2,3,3,3,4,5,5], "abacbeqwyyce"

class Solution:
    def longestPath(self, parent: List[int], s: str) -> int:
        tree = defaultdict(list)
        for end, start in enumerate(parent):
            tree[start].append(end)
        
        ans = 1

        def dfs(node):
            nonlocal ans
            max1, max2 = 0, 0
            for child in tree[node]:
                value = dfs(child)
                if s[node] == s[child]: continue
                if value > max1:
                    max1, max2 = value, max1
                elif value > max2:
                    max2 = value
            ans = max(ans, max1 + max2 + 1)
            return max1 + 1

        dfs(0)

        return ans

> [name=Yen-Chi Chen][time=Sat, Jan 14, 2023]

### Reference

[回到題目列表](https://hackmd.io/@Marsgoat/leetcode_every_day)