树形dp套路使用前提：

如果题目求解目标是S规则，则求解流程可以定成以每一个节点为头节点的子树在S规则下的每一个答案，并且最终答案一定在其中
树形dp套路第一步：
以某个节点X为头节点的子树中，分析答案有哪些可能性，并且这种分析是以X的左子树、X的右子树和X整棵树的角度来考虑可能性的
树形dp套路第二步：
根据第一步的可能性分析，列出所有需要的信息
树形dp套路第三步：
合并第二步的信息，对左树和右树提出同样的要求，并写出信息结构
树形dp套路第四步：
设计递归函数，递归函数是处理以X为头节点的情况下的答案。包括设计递归的basecase，默认直接得到左树和右树的所有信息，以及把可能性做整合，并且要返回第三步的信息结构这四个小步骤

二叉树节点间的最大距离问题

从二叉树的节点a出发，可以向上或者向下走，但沿途的节点只能经过一次，到达节点b时路径上的节点个数叫作a到b的距离，那么二叉树任何两个节点之间都有距离，求整棵树上的最大距离。

  1. public class MaxDistanceInTree {
  3.     public static class Node {
  4.         public int value;
  5.         public Node left;
  6.         public Node right;
  8.         public Node(int data) {
  9.             this.value = data;
  10.         }
  11.     }
  13.     public static int maxDistance(Node head) {
  14.         int[] record = new int[1];
  15.         return posOrder(head, record);
  16.     }
  18.     public static class ReturnType{
  19.         public int maxDistance;
  20.         public int h;
  22.         public ReturnType(int m, int h) {
  23.             this.maxDistance = m;;
  24.             this.h = h;
  25.         }
  26.     }
  28.     // 返回以x为头的整棵树，两个信息
  29.     public static ReturnType process(Node head) {
  30.         if(head == null) {
  31.             return new ReturnType(0,0);
  32.         }
  33.         ReturnType leftReturnType = process(head.left);
  34.         ReturnType rightReturnType = process(head.right);
  35.         int includeHeadDistance = leftReturnType.h + 1 + rightReturnType.h;
  36.         int p1 = leftReturnType.maxDistance;
  37.         int p2 = rightReturnType.maxDistance;
  38.         int resultDistance = Math.max(Math.max(p1, p2), includeHeadDistance);
  39.         int hitself  = Math.max(leftReturnType.h, leftReturnType.h) + 1;
  40.         return new ReturnType(resultDistance, hitself);
  41.     }
  43.     public static int posOrder(Node head, int[] record) {
  44.         if (head == null) {
  45.             record[0] = 0;
  46.             return 0;
  47.         }
  48.         int lMax = posOrder(head.left, record);
  49.         int maxfromLeft = record[0];
  50.         int rMax = posOrder(head.right, record);
  51.         int maxFromRight = record[0];
  52.         int curNodeMax = maxfromLeft + maxFromRight + 1;
  53.         record[0] = Math.max(maxfromLeft, maxFromRight) + 1;
  54.         return Math.max(Math.max(lMax, rMax), curNodeMax);
  55.     }
  57.     public static void main(String[] args) {
  58.         Node head1 = new Node(1);
  59.         head1.left = new Node(2);
  60.         head1.right = new Node(3);
  61.         head1.left.left = new Node(4);
  62.         head1.left.right = new Node(5);
  63.         head1.right.left = new Node(6);
  64.         head1.right.right = new Node(7);
  65.         head1.left.left.left = new Node(8);
  66.         head1.right.left.right = new Node(9);
  67.         System.out.println(maxDistance(head1));
  69.         Node head2 = new Node(1);
  70.         head2.left = new Node(2);
  71.         head2.right = new Node(3);
  72.         head2.right.left = new Node(4);
  73.         head2.right.right = new Node(5);
  74.         head2.right.left.left = new Node(6);
  75.         head2.right.right.right = new Node(7);
  76.         head2.right.left.left.left = new Node(8);
  77.         head2.right.right.right.right = new Node(9);
  78.         System.out.println(maxDistance(head2));
  79.     }
  80. }

派对的最大快乐值

image.png

public class MaxHappy {

    public static int maxHappy(int[][] matrix) {
        int[][] dp = new int[matrix.length][2];
        boolean[] visited = new boolean[matrix.length];
        int root = 0;
        for (int i = 0; i < matrix.length; i++) {
            if (i == matrix[i][0]) {
                root = i;
            }
        }
        process(matrix, dp, visited, root);
        return Math.max(dp[root][0], dp[root][1]);
    }

    public static void process(int[][] matrix, int[][] dp, boolean[] visited, int root) {
        visited[root] = true;
        dp[root][1] = matrix[root][1];
        for (int i = 0; i < matrix.length; i++) {
            if (matrix[i][0] == root && !visited[i]) {
                process(matrix, dp, visited, i);
                dp[root][1] += dp[i][0];
                dp[root][0] += Math.max(dp[i][1], dp[i][0]);
            }
        }
    }

    public static void main(String[] args) {
        int[][] matrix = { { 1, 8 }, { 1, 9 }, { 1, 10 } };
        System.out.println(maxHappy(matrix));
    }
}