class079 树型dp-下【算法】

package class079;
import java.util.ArrayList;
// 到达首都的最少油耗
// 给你一棵 n 个节点的树（一个无向、连通、无环图）
// 每个节点表示一个城市，编号从 0 到 n - 1 ，且恰好有 n - 1 条路
// 0 是首都。给你一个二维整数数组 roads
// 其中 roads[i] = [ai, bi] ，表示城市 ai 和 bi 之间有一条 双向路
// 每个城市里有一个代表，他们都要去首都参加一个会议
// 每座城市里有一辆车。给你一个整数 seats 表示每辆车里面座位的数目
// 城市里的代表可以选择乘坐所在城市的车，或者乘坐其他城市的车
// 相邻城市之间一辆车的油耗是一升汽油
// 请你返回到达首都最少需要多少升汽油
// 测试链接 : https://leetcode.cn/problems/minimum-fuel-cost-to-report-to-the-capital/
public class Code01_MinimumFuelCost {
  public static long minimumFuelCost(int[][] roads, int seats) {
    int n = roads.length + 1;
    ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
    for (int i = 0; i < n; i++) {
      graph.add(new ArrayList<>());
    }
    for (int[] r : roads) {
      graph.get(r[0]).add(r[1]);
      graph.get(r[1]).add(r[0]);
    }
    int[] size = new int[n];
    long[] cost = new long[n];
    f(graph, seats, 0, -1, size, cost);
    return cost[0];
  }
  // 根据图，当前来到u，u的父节点是p
  // 遍历完成后，请填好size[u]、cost[u]
  public static void f(ArrayList<ArrayList<Integer>> graph, int seats, int u, int p, int[] size, long[] cost) {
    size[u] = 1;
    for (int v : graph.get(u)) {
      if (v != p) {
        f(graph, seats, v, u, size, cost);
        size[u] += size[v];
        cost[u] += cost[v];
        // a/b向上取整，可以写成(a+b-1)/b
        // (size[v]+seats-1) / seats = size[v] / seats 向上取整
        cost[u] += (size[v] + seats - 1) / seats;
      }
    }
  }
}

package class079;
import java.util.ArrayList;
// 相邻字符不同的最长路径
// 给你一棵 树（即一个连通、无向、无环图），根节点是节点 0
// 这棵树由编号从 0 到 n - 1 的 n 个节点组成
// 用下标从 0 开始、长度为 n 的数组 parent 来表示这棵树
// 其中 parent[i] 是节点 i 的父节点
// 由于节点 0 是根节点，所以 parent[0] == -1
// 另给你一个字符串 s ，长度也是 n ，其中 s[i] 表示分配给节点 i 的字符
// 请你找出路径上任意一对相邻节点都没有分配到相同字符的 最长路径
// 并返回该路径的长度
// 测试链接 : https://leetcode.cn/problems/longest-path-with-different-adjacent-characters/
public class Code02_LongestPathWithDifferentAdjacent {
  public static int longestPath(int[] parent, String str) {
    int n = parent.length;
    char[] s = str.toCharArray();
    ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
    for (int i = 0; i < n; i++) {
      graph.add(new ArrayList<>());
    }
    for (int i = 1; i < n; i++) {
      graph.get(parent[i]).add(i);
    }
    return f(s, graph, 0).maxPath;
  }
  public static class Info {
    public int maxPathFromHead; // 一定要从头节点出发的情况下，相邻字符不等的最长路径长度
    public int maxPath; // 整棵树上，相邻字符不等的最长路径长度
    public Info(int a, int b) {
      maxPathFromHead = a;
      maxPath = b;
    }
  }
  public static Info f(char[] s, ArrayList<ArrayList<Integer>> graph, int u) {
    if (graph.get(u).isEmpty()) {
      // u节点是叶
      return new Info(1, 1);
    }
    int max1 = 0; // 下方最长链
    int max2 = 0; // 下方次长链
    int maxPath = 1;
    for (int v : graph.get(u)) {
      Info nextInfo = f(s, graph, v);
      maxPath = Math.max(maxPath, nextInfo.maxPath);
      if (s[u] != s[v]) {
        if (nextInfo.maxPathFromHead > max1) {
          max2 = max1;
          max1 = nextInfo.maxPathFromHead;
        } else if (nextInfo.maxPathFromHead > max2) {
          max2 = nextInfo.maxPathFromHead;
        }
      }
    }
    int maxPathFromHead = max1 + 1;
    maxPath = Math.max(maxPath, max1 + max2 + 1);
    return new Info(maxPathFromHead, maxPath);
  }
}

package class079;
// 移除子树后的二叉树高度
// 给你一棵 二叉树 的根节点 root ，树中有 n 个节点
// 每个节点都可以被分配一个从 1 到 n 且互不相同的值
// 另给你一个长度为 m 的数组 queries
// 你必须在树上执行 m 个 独立 的查询，其中第 i 个查询你需要执行以下操作：
// 从树中 移除 以 queries[i] 的值作为根节点的子树
// 题目所用测试用例保证 queries[i] 不等于根节点的值
// 返回一个长度为 m 的数组 answer
// 其中 answer[i] 是执行第 i 个查询后树的高度
// 注意：
// 查询之间是独立的，所以在每个查询执行后，树会回到其初始状态
// 树的高度是从根到树中某个节点的 最长简单路径中的边数
// 测试链接 : https://leetcode.cn/problems/height-of-binary-tree-after-subtree-removal-queries/
public class Code03_HeightRemovalQueries {
  // 不要提交这个类
  public static class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
  }
  // 提交如下的方法
  public static final int MAXN = 100010;
  // 下标为节点的值
  public static int[] dfn = new int[MAXN];
  // 下标为dfn序号
  public static int[] deep = new int[MAXN];
  // 下标为dfn序号
  public static int[] size = new int[MAXN];
  public static int[] maxl = new int[MAXN];
  public static int[] maxr = new int[MAXN];
  public static int dfnCnt;
  public static int[] treeQueries(TreeNode root, int[] queries) {
    dfnCnt = 0;
    f(root, 0);
    for (int i = 1; i <= dfnCnt; i++) {
      maxl[i] = Math.max(maxl[i - 1], deep[i]);
    }
    maxr[dfnCnt + 1] = 0;
    for (int i = dfnCnt; i >= 1; i--) {
      maxr[i] = Math.max(maxr[i + 1], deep[i]);
    }
    int m = queries.length;
    int[] ans = new int[m];
    for (int i = 0; i < m; i++) {
      int leftMax = maxl[dfn[queries[i]] - 1];
      int rightMax = maxr[dfn[queries[i]] + size[dfn[queries[i]]]];
      ans[i] = Math.max(leftMax, rightMax);
    }
    return ans;
  }
  // 来到x节点，从头节点到x节点经过了k条边
  public static void f(TreeNode x, int k) {
    int i = ++dfnCnt;
    dfn[x.val] = i;
    deep[i] = k;
    size[i] = 1;
    if (x.left != null) {
      f(x.left, k + 1);
      size[i] += size[dfn[x.left.val]];
    }
    if (x.right != null) {
      f(x.right, k + 1);
      size[i] += size[dfn[x.right.val]];
    }
  }
}

package class079;
import java.util.ArrayList;
import java.util.Arrays;
// 从树中删除边的最小分数
// 存在一棵无向连通树，树中有编号从0到n-1的n个节点，以及n-1条边
// 给你一个下标从0开始的整数数组nums长度为n，其中nums[i]表示第i个节点的值
// 另给你一个二维整数数组edges长度为n-1
// 其中 edges[i] = [ai, bi] 表示树中存在一条位于节点 ai 和 bi 之间的边
// 删除树中两条不同的边以形成三个连通组件，对于一种删除边方案，定义如下步骤以计算其分数：
// 分别获取三个组件每个组件中所有节点值的异或值
// 最大 异或值和 最小 异或值的 差值 就是这种删除边方案的分数
// 返回可能的最小分数
// 测试链接 : https://leetcode.cn/problems/minimum-score-after-removals-on-a-tree/
public class Code04_MinimumScoreAfterRemovals {
  public static int MAXN = 1001;
  // 下标为原始节点编号
  public static int[] dfn = new int[MAXN];
  // 下标为dfn序号
  public static int[] xor = new int[MAXN];
  // 下标为dfn序号
  public static int[] size = new int[MAXN];
  public static int dfnCnt;
  public static int minimumScore(int[] nums, int[][] edges) {
    int n = nums.length;
    ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
    for (int i = 0; i < n; i++) {
      graph.add(new ArrayList<>());
    }
    for (int[] edge : edges) {
      graph.get(edge[0]).add(edge[1]);
      graph.get(edge[1]).add(edge[0]);
    }
    Arrays.fill(dfn, 0, n, 0);
    dfnCnt = 0;
    f(nums, graph, 0);
    int m = edges.length;
    int ans = Integer.MAX_VALUE;
    for (int i = 0, a, b, pre, pos, sum1, sum2, sum3; i < m; i++) {
      a = Math.max(dfn[edges[i][0]], dfn[edges[i][1]]);
      for (int j = i + 1; j < m; j++) {
        b = Math.max(dfn[edges[j][0]], dfn[edges[j][1]]);
        if (a < b) {
          pre = a;
          pos = b;
        } else {
          pre = b;
          pos = a;
        }
        sum1 = xor[pos];
        // xor[1] : 整棵树的异或和
        // 因为头节点是0，一定拥有最小的dfn序号1
        // f函数调用的时候，也是从0节点开始的
        if (pos < pre + size[pre]) {
          sum2 = xor[pre] ^ xor[pos];
          sum3 = xor[1] ^ xor[pre];
        } else {
          sum2 = xor[pre];
          sum3 = xor[1] ^ sum1 ^ sum2;
        }
        ans = Math.min(ans, Math.max(Math.max(sum1, sum2), sum3) - Math.min(Math.min(sum1, sum2), sum3));
      }
    }
    return ans;
  }
  // 当前来到原始编号u，遍历u的整棵树
  public static void f(int[] nums, ArrayList<ArrayList<Integer>> graph, int u) {
    int i = ++dfnCnt;
    dfn[u] = i;
    xor[i] = nums[u];
    size[i] = 1;
    for (int v : graph.get(u)) {
      if (dfn[v] == 0) {
        f(nums, graph, v);
        xor[i] ^= xor[dfn[v]];
        size[i] += size[dfn[v]];
      }
    }
  }
}

package class079;
// 选课
// 在大学里每个学生，为了达到一定的学分，必须从很多课程里选择一些课程来学习
// 在课程里有些课程必须在某些课程之前学习，如高等数学总是在其它课程之前学习
// 现在有 N 门功课，每门课有个学分，每门课有一门或没有直接先修课
// 若课程 a 是课程 b 的先修课即只有学完了课程 a，才能学习课程 b
// 一个学生要从这些课程里选择 M 门课程学习
// 问他能获得的最大学分是多少
// 测试链接 : https://www.luogu.com.cn/problem/P2014
// 请同学们务必参考如下代码中关于输入、输出的处理
// 这是输入输出处理效率很高的写法
// 提交以下的code，提交时请把类名改成"Main"，可以直接通过
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.util.ArrayList;
// 普通解法，邻接表建图 + 相对好懂的动态规划
// 几乎所有题解都是普通解法的思路，只不过优化了常数时间、做了空间压缩
// 但时间复杂度依然是O(n * 每个节点的孩子平均数量 * m的平方)
public class Code05_CourseSelection1 {
  public static int MAXN = 301;
  public static int[] nums = new int[MAXN];
  public static ArrayList<ArrayList<Integer>> graph;
  static {
    graph = new ArrayList<>();
    for (int i = 0; i < MAXN; i++) {
      graph.add(new ArrayList<>());
    }
  }
  public static int[][][] dp = new int[MAXN][][];
  public static int n, m;
  public static void build(int n) {
    for (int i = 0; i <= n; i++) {
      graph.get(i).clear();
    }
  }
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StreamTokenizer in = new StreamTokenizer(br);
    PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
    while (in.nextToken() != StreamTokenizer.TT_EOF) {
      // 节点编号从0~n
      n = (int) in.nval;
      in.nextToken();
      m = (int) in.nval + 1;
      build(n);
      for (int i = 1, pre; i <= n; i++) {
        in.nextToken();
        pre = (int) in.nval;
        graph.get(pre).add(i);
        in.nextToken();
        nums[i] = (int) in.nval;
      }
      out.println(compute());
    }
    out.flush();
    out.close();
    br.close();
  }
  public static int compute() {
    for (int i = 0; i <= n; i++) {
      dp[i] = new int[graph.get(i).size() + 1][m + 1];
    }
    for (int i = 0; i <= n; i++) {
      for (int j = 0; j < dp[i].length; j++) {
        for (int k = 0; k <= m; k++) {
          dp[i][j][k] = -1;
        }
      }
    }
    return f(0, graph.get(0).size(), m);
  }
  // 当前来到i号节点为头的子树
  // 只在i号节点、及其i号节点下方的前j棵子树上挑选节点
  // 一共挑选k个节点，并且保证挑选的节点连成一片
  // 返回最大的累加和
  public static int f(int i, int j, int k) {
    if (k == 0) {
      return 0;
    }
    if (j == 0 || k == 1) {
      return nums[i];
    }
    if (dp[i][j][k] != -1) {
      return dp[i][j][k];
    }
    int ans = f(i, j - 1, k);
    // 第j棵子树头节点v 
    int v = graph.get(i).get(j - 1);
    for (int s = 1; s < k; s++) {
      ans = Math.max(ans, f(i, j - 1, k - s) + f(v, graph.get(v).size(), s));
    }
    dp[i][j][k] = ans;
    return ans;
  }
}

package class079;
// 选课
// 在大学里每个学生，为了达到一定的学分，必须从很多课程里选择一些课程来学习
// 在课程里有些课程必须在某些课程之前学习，如高等数学总是在其它课程之前学习
// 现在有 N 门功课，每门课有个学分，每门课有一门或没有直接先修课
// 若课程 a 是课程 b 的先修课即只有学完了课程 a，才能学习课程 b
// 一个学生要从这些课程里选择 M 门课程学习
// 问他能获得的最大学分是多少
// 测试链接 : https://www.luogu.com.cn/problem/P2014
// 请同学们务必参考如下代码中关于输入、输出的处理
// 这是输入输出处理效率很高的写法
// 提交以下的code，提交时请把类名改成"Main"，可以直接通过
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.util.Arrays;
// 最优解，链式前向星建图 + dfn序的利用 + 巧妙定义下的尝试
// 时间复杂度O(n*m)，觉得难可以跳过，这个最优解是非常巧妙和精彩的！
public class Code05_CourseSelection2 {
  public static int MAXN = 301;
  public static int[] nums = new int[MAXN];
  // 链式前向星建图
  public static int edgeCnt;
  public static int[] head = new int[MAXN];
  public static int[] next = new int[MAXN];
  public static int[] to = new int[MAXN];
  // dfn的计数
  public static int dfnCnt;
  // 下标为dfn序号
  public static int[] val = new int[MAXN + 1];
  // 下标为dfn序号
  public static int[] size = new int[MAXN + 1];
  // 动态规划表
  public static int[][] dp = new int[MAXN + 2][MAXN];
  public static int n, m;
  public static void build(int n, int m) {
    edgeCnt = 1;
    dfnCnt = 0;
    Arrays.fill(head, 0, n + 1, 0);
    Arrays.fill(dp[n + 2], 0, m + 1, 0);
  }
  public static void addEdge(int u, int v) {
    next[edgeCnt] = head[u];
    to[edgeCnt] = v;
    head[u] = edgeCnt++;
  }
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StreamTokenizer in = new StreamTokenizer(br);
    PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
    while (in.nextToken() != StreamTokenizer.TT_EOF) {
      n = (int) in.nval;
      in.nextToken();
      m = (int) in.nval;
      build(n, m);
      for (int i = 1; i <= n; i++) {
        in.nextToken();
        addEdge((int) in.nval, i);
        in.nextToken();
        nums[i] = (int) in.nval;
      }
      out.println(compute());
    }
    out.flush();
    out.close();
    br.close();
  }
  public static int compute() {
    f(0);
    // 节点编号0 ~ n，dfn序号范围1 ~ n+1
    // 接下来的逻辑其实就是01背包！不过经历了很多转化
    // 整体的顺序是根据dfn序来进行的，从大的dfn序，遍历到小的dfn序
    // dp[i][j] : i ~ n+1 范围的节点，选择j个节点一定要形成有效结构的情况下，最大的累加和
    // 怎么定义有效结构？重点！重点！重点！
    // 假设i ~ n+1范围上，目前所有头节点的上方，有一个总的头节点
    // i ~ n+1范围所有节点，选出来j个节点的结构，
    // 挂在这个假想的总头节点之下，是一个连续的结构，没有断开的情况
    // 那么就说，i ~ n+1范围所有节点，选出来j个节点的结构是一个有效结构
    for (int i = n + 1; i >= 2; i--) {
      for (int j = 1; j <= m; j++) {
        dp[i][j] = Math.max(dp[i + size[i]][j], val[i] + dp[i + 1][j - 1]);
      }
    }
    // dp[2][m] : 2 ~ n范围上，选择m个节点一定要形成有效结构的情况下，最大的累加和
    // 最后来到dfn序为1的节点，一定是原始的0号节点
    // 原始0号节点下方一定挂着有效结构
    // 并且和补充的0号节点一定能整体连在一起，没有任何跳跃连接
    // 于是整个问题解决
    return nums[0] + dp[2][m];
  }
  // u这棵子树的节点数返回
  public static int f(int u) {
    int i = ++dfnCnt;
    val[i] = nums[u];
    size[i] = 1;
    for (int ei = head[u], v; ei > 0; ei = next[ei]) {
      v = to[ei];
      size[i] += f(v);
    }
    return size[i];
  }
}