Tree-DP

337. 打家劫舍 III

方法一：树形DP

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int rob(TreeNode root) {
        int[] res = dfs(root);
        return Math.max(res[0], res[1]);  // 选或不选   
    }
    
    public int[] dfs(TreeNode root) {
        if (root == null)
            return new int[2];
        int[] left = dfs(root.left);
        int[] right = dfs(root.right);
        int rob = root.val + left[1] + right[1]; 
        int pass = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
        return new int[]{rob, pass};   
    }
}

2646. 最小化旅行的价格总和

方法一：树形DP

class Solution {
    public int minimumTotalPrice(int n, int[][] edges, int[] price, int[][] trips) {
        // 建图
        this.price = price;
        graph = new List[n];
        for (int i = 0; i < n; ++i)
            graph[i] = new ArrayList<>();
        for (int[] edge : edges) {
            int from = edge[0], to = edge[1];
            graph[from].add(to);
            graph[to].add(from);
        }
        count = new int[n];
        // 获取每个节点经过的次数
        for (int[] trip : trips)
            dfs(trip[0], -1, trip[1]);
        // 类似打家劫舍：打折或者不打折
        // 随便选一个点作为根节点，所有情况都会考虑到
        int[] res = dfs2(0, -1);
        return Math.min(res[0], res[1]);
    }

    private int[] dfs2(int cur, int parent) {
        int notHalve = 0, halve = 0;
        for (int next : graph[cur]) {
            if (next != parent) {
                int[] arr = dfs2(next, cur);
                int nh = arr[0], h = arr[1];
                notHalve += Math.min(nh, h);
                halve += nh;
            }
        }
        notHalve += count[cur] * price[cur];
        halve += (count[cur] * price[cur]) / 2;
        return new int[]{notHalve, halve};
    }

    int[] count, price;
    List<Integer>[] graph;
    private boolean dfs(int cur, int parent, int end) {
        if (cur == end) {
            count[cur]++;
            return true;
        }
        for (int next : graph[cur]) {
            if (next != parent && dfs(next, cur, end)) {
                count[cur]++;
                return true;
            }
        }
        return false;
    }
}

1377. T 秒后青蛙的位置

方法一：树形DP

思路：如果在给定步数t内找到target，则返回true，“归”的时候将概率prob / 当前节点的子树个数

特判根节点情况

(leftStep >= 0 && graph[cur].size() <= 1)表示走到根节点，但是步数没用完，可以原地起跳

class Solution {
    public double frogPosition(int n, int[][] edges, int t, int target) {
        if (n == 1 && target == 1)
            return 1.0;
        else if (target == 1 && t > 1)
            return 0.0;
        this.n = n;
        this.t = t;
        this.target = target;
        graph = new List[n + 1];
        Arrays.setAll(graph, o -> new ArrayList<>());
        for (int[] edge : edges) {
            int from = edge[0], to = edge[1];
            graph[from].add(to);
            graph[to].add(from);
        }
        if (!findPath(1, -1, t))
            return 0;
        return prob;
    }

    private boolean findPath(int cur, int parent, int leftStep) {
        // (leftStep >= 0 && graph[cur].size() <= 1)表示走到根节点，但是步数没用完，可以原地起跳
        if (cur == target && (leftStep == 0 || (leftStep >= 0 && graph[cur].size() <= 1))) 
            return true;
        for (int next : graph[cur]) {
            if (next != parent && findPath(next, cur, leftStep - 1)) {
                if (parent == -1) // root
                    prob /= graph[cur].size();
                else
                    prob /= (graph[cur].size() - 1);
                return true;
            }
        }
        return false;
    }

    List<Integer>[] graph;
    int n, t, target;
    double prob = 1.0;
}

2467. 树上最大得分和路径

方法一：树形DP

class Solution {
    public int mostProfitablePath(int[][] edges, int bob, int[] amount) {
        n = edges.length + 1;
        graph = new List[n];
        this.amount = amount;
        Arrays.setAll(graph, o -> new ArrayList<>());
        time = new int[n];
        Arrays.fill(time, n);
        for (int[] edge : edges) {
            int from = edge[0], to = edge[1];
            graph[from].add(to);
            graph[to].add(from);
        }
        graph[0].add(-1);
        getDistFromRoot(bob, -1, 0);
        dfs(0, -1, 0, 0);
        return res;
    }

    private void dfs(int alice, int parent, int aliceTime, int score) {
        if (aliceTime == time[alice])
            score += amount[alice] / 2;
        if (aliceTime < time[alice])
            score += amount[alice];
        if (graph[alice].size() == 1) {
            res = Math.max(res, score);
            return;
        }
        for (int next : graph[alice])
            if (next != parent)
                dfs(next, alice, aliceTime + 1, score);
    }


    private boolean getDistFromRoot(int cur, int parent, int t) {
        if (cur == 0) {
            time[cur] = t;
            return true;
        }
        for (int next : graph[cur]) {
            if (next != parent && getDistFromRoot(next, cur, t + 1)) {
                time[cur] = t;
                return true;
            }
        }
        return false;

    }

    List<Integer>[] graph;
    int[] time;
    int n;
    int[] amount;
    int res = Integer.MIN_VALUE;
}

import java.util.*;

public class _5 {

    public static void main(String[] args) {
        new _5().solve();
    }
    int n;
    int[] v;
    List<List<Integer>> graph = new ArrayList<>();
    void solve() {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        v = new int[n+1];
        for (int i = 1; i <= n; i++) {
            v[i] = sc.nextInt();
        }
        for (int i = 0; i <= n; i++) graph.add(new LinkedList<>());

        int res = 0;
        for (int i = 0 ; i < n  - 1; i ++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            graph.get(a).add(b);
            graph.get(b).add(a);
        }
        dp = new int[n+1][2];
        dfs(1,-1);
        System.out.println(Math.max(dp[1][0], dp[1][1]));
    }

    int[][] dp; //node 0不染色 1染色

    void dfs(int node, int pre) {
        for (int next : graph.get(node)) {
            if (next != pre) {
                dfs(next,node);
            }
        }

        //不染色
        for (int next : graph.get(node)) {
            if (next != pre) {
                dp[node][0] += Math.max(dp[next][0], dp[next][1]) ;
            }
        }

        for (int next : graph.get(node)) {
            if (next != pre) {
                if (isAns(v[next], v[node])) dp[node][1] = Math.max(dp[node][0] - Math.max(dp[next][0], dp[next][1])+2+dp[next][0], dp[node][1]);
            }
        }
    }

    boolean isAns(int a, int b) {
        if (a < 0 || b < 0) return false;
        long c = a*b;
        int sq = (int) Math.sqrt(c);
        return sq*sq == c;
    }

}

1372. 二叉树中的最长交错路径

方法一：树形DP

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    Map<TreeNode, Integer> f = new HashMap<>(), g = new HashMap<>();
    int res = 0;
    public int longestZigZag(TreeNode root) {
        if (root == null)
            return 0;
        f.put(root, 0);
        g.put(root, 0);
        dfs(root, null);
        for (TreeNode t : f.keySet())
            res = Math.max(res, Math.max(f.get(t), g.get(t)));
        return res;
    }

    public void dfs(TreeNode root, TreeNode pre) {
        if (root == null)
            return;
        if (pre != null) {
            if (root == pre.left) {
                f.put(root, g.get(pre) + 1);
                g.put(root, 0);
            }
            else {
                f.put(root, 0);
                g.put(root, f.get(pre) + 1);
            }
        }
        dfs(root.left, root);
        dfs(root.right, root);
    }
    
}

方法二：DFS(post)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    int res = 0;
    public int longestZigZag(TreeNode root) {
        if (root == null)
            return 0;
        dfs(root, null);
        return res;
    }

    public int dfs(TreeNode root, TreeNode pre) {
        if (root == null)
            return 0;
        int l = dfs(root.left, root);
        int r = dfs(root.right, root);
        if (pre != null) {
            if (root == pre.left) {
                res = Math.max(res, r + 1);
                return r + 1;
            }
            else {
                res = Math.max(res, l + 1);
                return l + 1;
            }
        }
        return Math.max(l, r) + 1;
    }
    
}

方法三：DFS

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    int res = 0;
    public int longestZigZag(TreeNode root) {
        dfs(root);
        return res;
    }

    public int[] dfs(TreeNode root) {
        if (root == null)
            return new int[]{-1, -1};
        int l = dfs(root.left)[1] + 1;
        int r = dfs(root.right)[0] + 1;
        res = Math.max(res, Math.max(l, r));
        return new int[]{l, r};
    }
    
}