# 2246. Longest Path With Different Adjacent Characters
###### tags: `Leetcode` `Hard` `Tree`
Link: https://leetcode.com/problems/longest-path-with-different-adjacent-characters/
## 思路
和[2049. Count Nodes With the Highest Score](https://hackmd.io/tTfQSMKxRoKh7xAlV3PwHA)很像
先把array用```List<List<Integer>>```变成tree 然后做dfs
## Code

class Solution {
    int maxLen = 0;
    public int longestPath(int[] parent, String s) {
        List<List<Integer>> tree = new ArrayList<>();
        for(int p:parent) tree.add(new ArrayList<>());
        for(int i=1; i<parent.length; i++){
            tree.get(parent[i]).add(i);
        }
        dfs(tree, s, 0);
        return maxLen;
    }
    private int dfs(List<List<Integer>> tree, String s, int root){
        int[] len = new int[2];
        for(int i=0; i<tree.get(root).size(); i++){
            int tempLen = dfs(tree, s, tree.get(root).get(i));
            if(s.charAt(root)==s.charAt(tree.get(root).get(i))) tempLen = 0;
            
            if(tempLen>len[0] && tempLen>len[1]){
                len[1] = len[0];
                len[0] = tempLen;
            }
            else if(tempLen>len[1]) len[1] = tempLen; 
        }
        maxLen = Math.max(maxLen, len[0]+len[1]+1);
        return len[0]+1;
    }
}