DP 树形 换根 - wenzhoullq/leetcode GitHub Wiki

int[] ans = new int[2];//0是取,1是不取
ans[0] = root.val + left[1] + right[1];
ans[1] = Math.max(left[0],left[1])+Math.max(right[0],right[1]);

    List<Integer>[] list ;
    public int longestPath(int[] parent, String s) {
        this.parent = parent;
        str = s.toCharArray();
        n = parent.length;
        list = new List[n];
        Arrays.fill(list,e->new LinkedList<>());
        for(){//建图
            int x , y;
            list[x].add(y)
            list[y].add(x);
        }
       int[] ans =  dfs(0,-1);
        return Math.min/max(ans[0],ans[1]);
    }
    int[] dfs(int cur,int fa){
        for(int son :list[cur]){
            if(fa==son) continue;
            int[] c = dfs(son,cur);
            //如果是类似于树的直径的,那么ans需要在这里比较
            get += c[1];
            notget +=Math.min/max(c[0],c[1]);
        }
        ans[0] = get;
        ans[1] = notget; 
        return ans;
    }