11.动态规划：树形DP问题、树上最大独立集、树上最小支配集、换根DP、树上倍增（LCA）【灵神基础精讲】

树形DP问题

回溯和树形DP的区别（什么时候需要return结果？）：对于回溯，通常是在「递」的过程中增量地构建答案，并在失败时能够回退，例如八皇后。对于递归，是把原问题分解为若干个相似的子问题，通常会在「归」的过程中有一些计算。如果一个递归能考虑用记忆化来优化，就需要 return 一个值并加以保存。

一、树的直径（二叉树==>一般树）

树形DP①树的直径【基础算法精讲 23】

二叉树的直径：

• 复习：104. 二叉树的最大深度

• 边权型： 543. 二叉树的直径

• 点权型： 124. 二叉树的最大路径和

一般树的直径：

• 1245.树的直径
• 2246.相邻字符不同的最长路径

一篇文章解决所有二叉树路径问题：https://leetcode.cn/problems/diameter-of-binary-tree/solution/yi-pian-wen-zhang-jie-jue-suo-you-er-cha-6g00/

二叉树路径的问题大致可以分为两类：

一、自顶向下：这类题通常用深度优先搜索(DFS)和广度优先搜索(BFS)解决

二、非自顶而下：这类题目一般解题思路如下：设计一个辅助函数dfs调用自身求出以一个节点为根节点的左侧最长路径left和右侧最长路径right，那么经过该节点的最长路径就是left+right
接着只需要从根节点开始dfs,不断比较更新全局变量即可

这类题型DFS注意点：

1、left,right代表的含义要根据题目所求设置，比如最长路径、最大路径和等等

2、全局变量res的初值设置是0还是INT_MIN要看题目节点是否存在负值,如果存在就用INT_MIN，否则就是0

3、注意两点之间路径为1，因此一个点是不能构成路径的

543. 二叉树的直径

难度简单1303

给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。

示例 :
给定二叉树

          1
         / \
        2   3
       / \     
      4   5    

返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。

**注意：**两结点之间的路径长度是以它们之间边的数目表示。

题解：

换个角度看直径

从一个叶子出发向上，在某个节点[拐弯]，向下到达另一个叶子得到了由两条链拼起来的路径。(也可能只有一条链)

算法

遍历二叉树，在计算最长链的同时，顺带把直径算出来。

• 在当前节点[拐弯]的直径长度 =左子的最长链 +右子的最长链 +2

• 返回给父节点的是以当前节点为根的子树的最长链 = max(左子树的最长链，右子树的最长链)+1。

class Solution {
    int res = 0;
    public int diameterOfBinaryTree(TreeNode root) {
        dfs(root);
        return res;
    }

    // private int dfs(TreeNode root){
    //     if(root.left == null && root.right == null){
    //         return 0; //不能是root == null 
    //     }
    //     // 获得左右子树的最长路径
    //     int left = root.left == null ? 0 : dfs(root.left) + 1;
    //     int right = root.right == null ? 0 : dfs(root.right) + 1;
    //     res = Math.max(res, left + right); 
    //     return Math.max(left, right); // 返回左右子树长度较长的那一个
    // }
    //零神写法：
    public int dfs(TreeNode node){
        if(node == null) 
            return -1; // 下面 +1 后，对于叶子节点就刚好是 0
        int leftlen = dfs(node.left) + 1; // 左子树最大链长+1
        int rightlen = dfs(node.right) + 1; // 右子树最大链长+1
        res = Math.max(res, leftlen + rightlen); // 两条链拼成路径
        return Math.max(leftlen, rightlen); // 当前子树最大链长
    }
}

124. 二叉树中的最大路径和

难度困难1919

二叉树中的 路径 被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。

路径和 是路径中各节点值的总和。

给你一个二叉树的根节点 root ，返回其 最大路径和 。

示例 1：

输入：root = [1,2,3]
输出：6
解释：最优路径是 2 -> 1 -> 3 ，路径和为 2 + 1 + 3 = 6

示例 2：

输入：root = [-10,9,20,null,null,15,7]
输出：42
解释：最优路径是 15 -> 20 -> 7 ，路径和为 15 + 20 + 7 = 42

提示：

• 树中节点数目范围是 [1, 3 * 104]
• -1000 <= Node.val <= 1000

题解：从边变成了点，实际上解法是一样的

算法：

遍历二叉树，在计算最大链和的同时，顺带更新答案的最大值。

在当前节点[拐弯]的最大路径和= 左子树最大链和 + 右子最大链和 +当前节点值。

返回给父节点的是 max(左子树最大链和，右子树最大链和)+ 当前节点值，如果这个值是负数，则返回 0。

class Solution {
    int res = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        dfs(root);
        return res;
    }

    public int dfs(TreeNode node){
        if(node == null) 
            return 0;
        int leftlen = dfs(node.left);
        int rightlen = dfs(node.right);
        res = Math.max(res, leftlen + rightlen + node.val);
        return Math.max(0, Math.max(leftlen, rightlen) + node.val);
    }
}

🎱(树的直径)2246. 相邻字符不同的最长路径

难度困难50

给你一棵 树（即一个连通、无向、无环图），根节点是节点 0 ，这棵树由编号从 0 到 n - 1 的 n 个节点组成。用下标从 0 开始、长度为 n 的数组 parent 来表示这棵树，其中 parent[i] 是节点 i 的父节点，由于节点 0 是根节点，所以 parent[0] == -1 。

另给你一个字符串 s ，长度也是 n ，其中 s[i] 表示分配给节点 i 的字符。

请你找出路径上任意一对相邻节点都没有分配到相同字符的 最长路径 ，并返回该路径的长度。

示例 1：

输入：parent = [-1,0,0,1,1,2], s = "abacbe"
输出：3
解释：任意一对相邻节点字符都不同的最长路径是：0 -> 1 -> 3 。该路径的长度是 3 ，所以返回 3 。
可以证明不存在满足上述条件且比 3 更长的路径。 

示例 2：

输入：parent = [-1,0,0,0], s = "aabc"
输出：3
解释：任意一对相邻节点字符都不同的最长路径是：2 -> 0 -> 3 。该路径的长度为 3 ，所以返回 3 。

提示：

• n == parent.length == s.length
• 1 <= n <= 105
• 对所有 i >= 1 ，0 <= parent[i] <= n - 1 均成立
• parent[0] == -1
• parent 表示一棵有效的树
• s 仅由小写英文字母组成

思考：

1、如何求树的直径？

• 思路一: 遍历 x 的子树，把最长链的长度都存到一个列表中，排序，取最大的两个

• 思路二: 遍历 x 的子树的同时求最长+次长

↓↓↓↓↓↓

2、如何一次遍历找到最长+次长?

• 如果次长在前面，最长在后面那么遍历到最长的时候就能算出最长+次长
• 如果最长在前面，次长在后面那么遍历到次长的时候就能算出最长+次长

一、求树的直径（本题是以parent数组表示的图）

• 求树的直径-树形DP模板

class Solution {
    List<Integer>[] g;
    String s;
    int ans;
    public int longestPath(int[] parent, String s) {
        this.s = s;
        int n = parent.length;
        g = new ArrayList[n];
        Arrays.setAll(g, e -> new ArrayList<>());
        for(int i = 1; i < n; i++)
            g[parent[i]].add(i);
        dfs(0);
        return ans + 1; // 求点的个数 = 边个数 + 1
    }

    public int dfs(int x){
        int maxlen = 0;// 记录x的最大链长
        for(int y : g[x]){
            int len = dfs(y) + 1;	// y为根节点的最大链长
            ans = Math.max(ans, maxlen + len); // 更新答案的最大链长（xy分别为最长和次长时的直径）
            maxlen = Math.max(maxlen, len); // 更新 x 的最大链长
        }
        return maxlen; // 返回x的最大链长
    }
}

二、2246题的解法

• 在求树的直径问题上加判断条件

class Solution {
    List<Integer>[] g;
    String s;
    int ans;
    public int longestPath(int[] parent, String s) {
        this.s = s;
        int n = parent.length;
        g = new ArrayList[n];
        Arrays.setAll(g, e -> new ArrayList<>());
        for(int i = 1; i < n; i++)
            g[parent[i]].add(i);
        dfs(0);
        return ans + 1; // 求点的个数 = 边个数 + 1
    }

    public int dfs(int x){
        int maxlen = 0;
        for(int y : g[x]){
            int len = dfs(y) + 1;
            // 条件：相邻节点不能分配到相同字符
            if(s.charAt(y) != s.charAt(x)){
                ans = Math.max(ans, maxlen + len); // 更新答案的最大链长
                maxlen = Math.max(maxlen, len); // 更新 x 的最大链长
            }   
        }
        return maxlen; // 返回x的最大链长
    }
}

如果x的邻居包含父节点(x节点)，在DFS中额外传入参数表示父节点：

class Solution {
    List<Integer>[] g;
    String s;
    int ans;
    public int longestPath(int[] parent, String s) {
        this.s = s;
        int n = parent.length;
        g = new ArrayList[n];
        Arrays.setAll(g, e -> new ArrayList<>());
        for(int i = 1; i < n; i++)
            g[parent[i]].add(i);
        dfs(0, -1);
        return ans + 1;
    }

    public int dfs(int x, int fa){
        int maxlen = 0;
        for(int y : g[x]){
            if(y == fa) continue; // y是x的父节点就跳过
            int len = dfs(y, x) + 1;
            // 条件：相邻节点不能分配到相同字符
            if(s.charAt(y) != s.charAt(x)){
                ans = Math.max(ans, maxlen + len); // 更新答案的最大链长
                maxlen = Math.max(maxlen, len); // 更新 x 的最大链长
            }   
        }
        return maxlen; // 返回x的节点个数
    }
}

二、树上最大独立集（打家劫舍Ⅲ）

树形DP如何思考？打家劫舍III【基础算法精讲 24】

树的最大独立集合：对于一颗无根树，选出尽量多的点使得任何两个结点均不相邻。

• 树上最大独立集问题（Maximum Independent Set Problem on Trees）：在给定的树中，找到一个具有最大节点数量的独立集。独立集是指在树中选择一组节点，使得这些节点两两之间没有边相连。换句话说，任何两个选择的节点之间都不存在直接连接。

• 树上最小支配集问题（Minimum Dominating Set Problem on Trees）：在给定的树中，找到一个具有最小节点数量的支配集。支配集是指在树中选择一组节点，使得每个未选择的节点要么与选择的节点相邻，要么本身就是选择的节点。换句话说，每个未选择的节点要么被选择的节点支配（与之相邻），要么本身就是选择的节点。

两个问题的目标相反：最大独立集问题追求选择尽可能多的节点，而最小支配集问题追求选择尽可能少的节点。

需要注意的是，在一棵树上，最小支配集的补集即为最大独立集。也就是说，最小支配集中的节点是覆盖了整个树的节点，而最大独立集中的节点则是不相互连接的节点。

337. 打家劫舍 III

难度中等1682

小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 root 。

除了 root 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。

给定二叉树的 root 。返回 在不触动警报的情况下 ，小偷能够盗取的最高金额 。

提示：

• 树的节点数在 [1, 104] 范围内
• 0 <= Node.val <= 104

题解：

1、选或不选

• 选当前节点：左右儿子都不能选

• 不选当前节点：左右儿子可选可不选

2、提炼状态

• 选当前节点时，以当前节点为根的子树最大点权和

• 不选当前节点时，以当前节点为根的子树最大点权和

3、转移方程

• 选 = 左不选 + 右不选 + 当前节点值

• 不选 =max(左选，左不选) + max(右选，右不选)

最终答案=max(根选，根不选）

class Solution {
    public int rob(TreeNode root) {
        int[] res = dfs(root);
        return Math.max(res[0], res[1]);
    }
    //   当前结点值：
    // res[0] : 选 = 左不选 + 右不选 + 当前节点值
    // res[1] : 不选 = max(左选,左不选) + max(右选,右不选)
    public int[] dfs(TreeNode node){
        if(node == null)
            return new int[]{0, 0};
        int[] left = dfs(node.left);
        int[] right = dfs(node.right);
        int[] res = new int[2];
        res[0] = left[1] + right[1] + node.val;
        res[1] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
        return res;
    }
}

三、树上最小支配集

968. 监控二叉树

难度困难625

给定一个二叉树，我们在树的节点上安装摄像头。

节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。

计算监控树的所有节点所需的最小摄像头数量。

示例 1：

输入：[0,0,null,0,0]
输出：1
解释：如图所示，一台摄像头足以监控所有节点。

示例 2：

输入：[0,0,null,0,null,0,null,null,0]
输出：2
解释：需要至少两个摄像头来监视树的所有节点。 上图显示了摄像头放置的有效位置之一。

提示：

1. 给定树的节点数的范围是 [1, 1000]。
2. 每个节点的值都是 0。

题解：这种题的话，需要实现节点之间信息的交流，二叉树有3种遍历，那就有3种信息交流的方式，前序的自上而下，后序的自下而上，中序的左上右下，根据题目要求，这题选用后续遍历是传递信息的最佳选择。需要传递的信息有三种：1.要求父节点安装相机；2.说自己有相机；3.自己不需要相机或空节点；那么，每个节点在接受了两个子节点的信息后，还要判断自己要向父节点传递哪种信息，如此层层向上传递，便解决了问题。

class Solution {
    int ans = 0;

    public int minCameraCover(TreeNode root) {
        if(dfs(root) == 2) ans += 1;
        return ans;
    }

    // 三种状态： 
    //      0 : 该节点安装了监视器
    //      1 : 该节点可观，但没有安装监视器
    //      2 : 该节点不可观
    public int dfs(TreeNode node){
        if(node == null)
            return 1;
        int left = dfs(node.left);
        int right = dfs(node.right);
        if(left == 2 || right == 2){
            ans += 1;
            return 0;
        } else if (left == 0 || right == 0){
            return 1;
        } else 
            return 2;
    }
}

四、换根DP问题

• 树形DP问题：树形DP是一种在树结构上应用动态规划的技巧。它通常用于解决与树有关的问题，例如计算树的直径、计算树的最长路径、计算树的最大权重等。树形DP的基本思路是从叶子节点开始，逐步向上计算节点的状态，利用子树的计算结果来更新当前节点的状态。 这种自底向上的递归计算可以通过递归函数或迭代方式实现。

• 换根DP问题：换根DP是树形DP的一种特殊情况，它解决的是当树的根节点发生改变时，树的状态发生的变化问题。在换根DP中，我们需要考虑树结构的变化对计算结果的影响。通常，我们会在树上选择一个节点作为新的根，并重新计算以该节点为根的子树的状态。然后，我们通过比较不同根节点下的计算结果，选择最优的结果作为最终答案。

换根DP问题可以看作是树形DP问题的一种应用场景，它强调了根节点的变化对问题解决的影响。换根DP常用于解决一些具有树形结构的问题，例如计算树的直径、计算树的最长路径和计算树的最大权重等。

总结起来，树形DP是一种在树结构上进行动态规划的技巧，而换根DP是树形DP的一种特殊情况，它解决的是树的根节点变化时的问题。

练习：换根 DP

• 310. 最小高度树（做法不止一种）

• 2581. 统计可能的树根数目

• Codeforces 771C. Bear and Tree Jumps（本题进阶版）

834. 树中距离之和

难度困难438

给定一个无向、连通的树。树中有 n 个标记为 0...n-1 的节点以及 n-1 条边 。

给定整数 n 和数组 edges ， edges[i] = [ai, bi]表示树中的节点 ai 和 bi 之间有一条边。

返回长度为 n 的数组 answer ，其中 answer[i] 是树中第 i 个节点与所有其他节点之间的距离之和。

示例 1:

输入: n = 6, edges = [[0,1],[0,2],[2,3],[2,4],[2,5]]
输出: [8,12,6,10,10,10]
解释: 树如图所示。
我们可以计算出 dist(0,1) + dist(0,2) + dist(0,3) + dist(0,4) + dist(0,5) 
也就是 1 + 1 + 2 + 2 + 2 = 8。 因此，answer[0] = 8，以此类推。

示例 2:

输入: n = 1, edges = []
输出: [0]

示例 3:

输入: n = 2, edges = [[1,0]]
输出: [1,1]

提示:

• 1 <= n <= 3 * 104
• edges.length == n - 1
• edges[i].length == 2
• 0 <= ai, bi < n
• ai != bi
• 给定的输入保证为有效的树

题解：https://leetcode.cn/problems/sum-of-distances-in-tree/solution/tu-jie-yi-zhang-tu-miao-dong-huan-gen-dp-6bgb/

暴力做法是，以点i为树根，从i出发 DFS 这棵树，那么i到j的距离就是j在这棵树的深度。所有点的深度之和就是 answer[i] (简称为 ans[i])。

但这样做，DFS 一次的时间是 O(n)，n 个点 DFS 一次，总时间就是 O(n^2)，会超时。如何优化呢?

问: 子树大小是怎么算的?

答: 先说二又树，子树 x 的大小等于左子树的大小，加上右子树的大小，再加上 1 (节点 x 本身) ，那么后序遍历这棵树，就可以算出每棵子树的大小。然后推广到一般树子树 x 的大小，等于 x 的所有儿子的子树大小之和，再加上 1 (节点 x 本身)。

问: 在 DFS 中，如何保证每个节点只递归访问一次?

答:通用做法是用一个 vis 数组标记访问过的点，如果某个点之前访问过，就不再递归访问。但对于树来说，一直向下递归，并不会遇到之前访问过的点，所以不需要 vis 数组。本题是无向树，除了根节点以外，其余每个点的邻居都包含其父节点，所以要避免访问父节点。我们可以定义 dfs(x,fa) 表示递归到节点 x 且 x 的节点为 fa。只要 x 的邻居 y ≠fa，就可以 dfs(y,x) 向下递归了。

问: 这种算法的本质是什么?

答: 以图中的这棵树为例，从[以 0 为根]换到[以 2 为根]时原来 2 的子节点还是 2 的子节点，原来 1的子节点还是 1 的子节点，唯一改变的是 0 和 2 的父子关系。由此可见，一对节点的距离的[变化量]应该是很小的，那么找出[变化量]的规律，就可以基于 ans[0] 算出 ans[2] 了。这种算法叫做换根 DP 。

class Solution {
    private List<Integer>[] g;
    private int[] ans, size;

    public int[] sumOfDistancesInTree(int n, int[][] edges) {
        g = new ArrayList[n]; // g[x] 表示 x 的所有邻居
        Arrays.setAll(g, e -> new ArrayList<>());
        for(int[] e : edges){
            int x = e[0], y = e[1];
            g[x].add(y);
            g[y].add(x);
        }
        ans = new int[n];
        // 这里是变化点，按照题目要求更改
        size = new int[n];
        dfs(0, -1, 0); // 计算ans[0], 在计算的同时，算出每颗子树的大小 size[i]
        reroot(0, -1); // 0 没有父节点 
        return ans;
    }

    private void dfs(int x, int fa, int depth){
        ans[0] += depth; // depth 为 0 到 x 的距离
        size[x] = 1;
        for(int y : g[x]){ // 遍历 x 的邻居 y
            if(y != fa){ // 避免访问父节点
                dfs(y, x, depth + 1); // x 是 y 的父节点
                // 这里是变化点，按照题目要求更改
                size[x] += size[y];  // 累加 x 的儿子 y 的子树大小
            }
        }
    }

    private void reroot(int x, int fa){
        for(int y : g[x]){ // 遍历 x 的邻居 y
            if(y != fa){ // 避免访问父节点
            	// 这里是变化点，按照题目要求更改
                ans[y] = ans[x] + g.length - 2 * size[y];
                reroot(y, x); // x 是 y 的父节点
            }
        }
    }
}

2858. 可以到达每一个节点的最少边反转次数

困难

给你一个 n 个点的 简单有向图 （没有重复边的有向图），节点编号为 0 到 n - 1 。如果这些边是双向边，那么这个图形成一棵 树 。

给你一个整数 n 和一个 二维 整数数组 edges ，其中 edges[i] = [ui, vi] 表示从节点 ui 到节点 vi 有一条 有向边 。

边反转 指的是将一条边的方向反转，也就是说一条从节点 ui 到节点 vi 的边会变为一条从节点 vi 到节点 ui 的边。

对于范围 [0, n - 1] 中的每一个节点 i ，你的任务是分别 独立 计算 最少 需要多少次 边反转 ，从节点 i 出发经过 一系列有向边 ，可以到达所有的节点。

请你返回一个长度为 n 的整数数组 answer ，其中 answer[i]表示从节点 i 出发，可以到达所有节点的 最少边反转 次数。

示例 1：

输入：n = 4, edges = [[2,0],[2,1],[1,3]]
输出：[1,1,0,2]
解释：上图表示了与输入对应的简单有向图。
对于节点 0 ：反转 [2,0] ，从节点 0 出发可以到达所有节点。
所以 answer[0] = 1 。
对于节点 1 ：反转 [2,1] ，从节点 1 出发可以到达所有节点。
所以 answer[1] = 1 。
对于节点 2 ：不需要反转就可以从节点 2 出发到达所有节点。
所以 answer[2] = 0 。
对于节点 3 ：反转 [1,3] 和 [2,1] ，从节点 3 出发可以到达所有节点。
所以 answer[3] = 2 。

示例 2：

输入：n = 3, edges = [[1,2],[2,0]]
输出：[2,0,1]
解释：上图表示了与输入对应的简单有向图。
对于节点 0 ：反转 [2,0] 和 [1,2] ，从节点 0 出发可以到达所有节点。
所以 answer[0] = 2 。
对于节点 1 ：不需要反转就可以从节点 2 出发到达所有节点。
所以 answer[1] = 0 。
对于节点 2 ：反转 [1,2] ，从节点 2 出发可以到达所有节点。
所以 answer[2] = 1 。

提示：

• 2 <= n <= 105
• edges.length == n - 1
• edges[i].length == 2
• 0 <= ui == edges[i][0] < n
• 0 <= vi == edges[i][1] < n
• ui != vi
• 输入保证如果边是双向边，可以得到一棵树。

换根DP

https://leetcode.cn/problems/minimum-edge-reversals-so-every-node-is-reachable/solutions/2445681/mo-ban-huan-gen-dppythonjavacgojs-by-end-8qiu/

class Solution {
    private List<int[]>[] g;
    private int[] ans, size;


    public int[] minEdgeReversals(int n, int[][] edges) {
        g = new ArrayList[n]; // g[x] 表示 x 的所有邻居
        Arrays.setAll(g, e -> new ArrayList<>());
        for(int[] e : edges){
            int x = e[0], y = e[1];
            g[x].add(new int[]{y, 1});
            g[y].add(new int[]{x, -1}); // 有向图，标记y到x为反向
        }
        ans = new int[n];
        dfs(0, -1); // 计算ans[0]
        reroot(0, -1); // 0 没有父节点 
        return ans;
    }

    private void dfs(int x, int fa){
        for(int[] e : g[x]){ // 遍历 x 的邻居 y
            int y = e[0], dir = e[1];
            if(y != fa){ // 避免访问父节点
                if(dir < 0) 
                    ans[0] += 1;
                dfs(y, x); // x 是 y 的父节点
            }
        }
    }

    private void reroot(int x, int fa){
        for(int[] e : g[x]){ // 遍历 x 的邻居 y
            int y = e[0], dir = e[1];
            if(y != fa){ // 避免访问父节点
            	// 这里是变化点，按照题目要求更改
                ans[y] = ans[x] + dir; // dir 就是 从 x 换到 y 的 变化量
                reroot(y, x); // x 是 y 的父节点
            }
        }
    }

}

2581. 统计可能的树根数目

难度困难34

Alice 有一棵 n 个节点的树，节点编号为 0 到 n - 1 。树用一个长度为 n - 1 的二维整数数组 edges 表示，其中 edges[i] = [ai, bi] ，表示树中节点 ai 和 bi 之间有一条边。

Alice 想要 Bob 找到这棵树的根。她允许 Bob 对这棵树进行若干次 猜测 。每一次猜测，Bob 做如下事情：

• 选择两个 不相等 的整数 u 和 v ，且树中必须存在边 [u, v] 。
• Bob 猜测树中 u 是 v 的 父节点 。

Bob 的猜测用二维整数数组 guesses 表示，其中 guesses[j] = [uj, vj] 表示 Bob 猜 uj 是 vj 的父节点。

Alice 非常懒，她不想逐个回答 Bob 的猜测，只告诉 Bob 这些猜测里面 至少 有 k 个猜测的结果为 true 。

给你二维整数数组 edges ，Bob 的所有猜测和整数 k ，请你返回可能成为树根的 节点数目 。如果没有这样的树，则返回 0。

示例 1：

输入：edges = [[0,1],[1,2],[1,3],[4,2]], guesses = [[1,3],[0,1],[1,0],[2,4]], k = 3
输出：3
解释：
根为节点 0 ，正确的猜测为 [1,3], [0,1], [2,4]
根为节点 1 ，正确的猜测为 [1,3], [1,0], [2,4]
根为节点 2 ，正确的猜测为 [1,3], [1,0], [2,4]
根为节点 3 ，正确的猜测为 [1,0], [2,4]
根为节点 4 ，正确的猜测为 [1,3], [1,0]
节点 0 ，1 或 2 为根时，可以得到 3 个正确的猜测。

示例 2：

输入：edges = [[0,1],[1,2],[2,3],[3,4]], guesses = [[1,0],[3,4],[2,1],[3,2]], k = 1
输出：5
解释：
根为节点 0 ，正确的猜测为 [3,4]
根为节点 1 ，正确的猜测为 [1,0], [3,4]
根为节点 2 ，正确的猜测为 [1,0], [2,1], [3,4]
根为节点 3 ，正确的猜测为 [1,0], [2,1], [3,2], [3,4]
根为节点 4 ，正确的猜测为 [1,0], [2,1], [3,2]
任何节点为根，都至少有 1 个正确的猜测。

提示：

• edges.length == n - 1
• 2 <= n <= 105
• 1 <= guesses.length <= 105
• 0 <= ai, bi, uj, vj <= n - 1
• ai != bi
• uj != vj
• edges 表示一棵有效的树。
• guesses[j] 是树中的一条边。
• guesses 是唯一的。
• 0 <= k <= guesses.length

题解：https://leetcode.cn/problems/count-number-of-possible-root-nodes/solution/huan-gen-dppythonjavacgo-by-endlesscheng-ccwy/

注意到，如果节点 x 和 y 之间有边，那么从[以 x 为根的树]变成[以 y 为根的树]，就只有[x,y] 和[y, x] 这两个猜测的正确性变了，其余猜测的正确性不变。

class Solution {
    /** 换根DP
    1. 把以 0 为根的才对次数算出来 cnt0
    2. 再跑一次dfs，计算以其他 节点 为根的猜对次数
    怎么计算？
        比如 根节点从 0 变到了 1
        如果有猜测[0, 1] 那么猜对次数减一
        如果有猜测[1, 0] 那么猜对次数加一
    
     */
    private List<Integer>[] g;
    private Set<Long> s = new HashSet<>();
    private int k, ans, cnt0;
    public int rootCount(int[][] edges, int[][] guesses, int k) {
        this.k = k;
        g = new ArrayList[edges.length+1];
        Arrays.setAll(g, e -> new ArrayList<>());
        for(int[] e : edges){
            int x = e[0], y = e[1];
            g[x].add(y);
            g[y].add(x); // 建图
        }
        for(int[] e : guesses){ // guesses 转换成哈希表，加快查询速度
            s.add((long) e[0] << 32 | e[1]); // 两个 4 字节数压缩成一个 8 字节数Long
        }
        dfs(0, -1);
        reroot(0,-1,cnt0);
        return ans;
    }

    private void dfs(int x, int fa){
        for(int y : g[x]){
            if(y != fa){
                if(s.contains((long) x << 32 | y)) // 以 0 为根时，猜对了
                    cnt0++;
                dfs(y,x);
            }
        }
    }

    private void reroot(int x, int fa, int cnt){
        if(cnt >= k) ans++;// 此时 cnt 就是以 x 为根时的猜对次数
        for(int y : g[x]){
            if(y != fa){
                int c = cnt;
                if(s.contains((long) x << 32 | y)) c--;// 原来是对的，现在错了
                if(s.contains((long) y << 32 | x)) c++;// 原来是对的，现在错了
                reroot(y,x,c);
            }
        }
    }
}

五、树上倍增算法

1483. 树节点的第 K 个祖先

难度困难134

给你一棵树，树上有 n 个节点，按从 0 到 n-1 编号。树以父节点数组的形式给出，其中 parent[i] 是节点 i 的父节点。树的根节点是编号为 0 的节点。

树节点的第 k 个祖先节点是从该节点到根节点路径上的第 k 个节点。

实现 TreeAncestor 类：

• TreeAncestor（int n， int[] parent） 对树和父数组中的节点数初始化对象。
• getKthAncestor``(int node, int k) 返回节点 node 的第 k 个祖先节点。如果不存在这样的祖先节点，返回 -1 。

示例 1：

输入：
["TreeAncestor","getKthAncestor","getKthAncestor","getKthAncestor"]
[[7,[-1,0,0,1,1,2,2]],[3,1],[5,2],[6,3]]

输出：
[null,1,0,-1]

解释：
TreeAncestor treeAncestor = new TreeAncestor(7, [-1, 0, 0, 1, 1, 2, 2]);

treeAncestor.getKthAncestor(3, 1);  // 返回 1 ，它是 3 的父节点
treeAncestor.getKthAncestor(5, 2);  // 返回 0 ，它是 5 的祖父节点
treeAncestor.getKthAncestor(6, 3);  // 返回 -1 因为不存在满足要求的祖先节点

提示：

• 1 <= k <= n <= 5 * 104
• parent[0] == -1 表示编号为 0 的节点是根节点。
• 对于所有的 0 < i < n ，0 <= parent[i] < n 总成立
• 0 <= node < n
• 至多查询 5 * 104 次

树上倍增算法

https://leetcode.cn/problems/kth-ancestor-of-a-tree-node/solution/mo-ban-jiang-jie-shu-shang-bei-zeng-suan-v3rw/

预处理出每个节点的第 2^i个祖先节点，即第 2,4,8.... 个祖先节点(注意 x 的第1 个祖先节点就是 parent[x]。由于任意 k 可以分解为若干不同的 2 的幂(例如 13 = 8+4+1)，所以只需要预处理出这些 2^i 祖先节点，就可以快速地到达任意第 k 个祖先节点

例如 k = 13 = 8+4+1 = 1101_(2)，可以先往上跳 8 步，再往上跳 4步和1步;也可以先往上跳1步，再往上跳 4 步和 8 步。无论如何跳，都只需要跳 3 次就能到达第 13 个祖先节点据此，可以得到下面的算法。

算法：

在构造函数 TreeAncestor 中，预处理出每个节点 x 的第 2^i 个祖先节点，记作 pa[x][i] (若第 2^i 个祖先节点不存在则 pa[x][i] = -1) 。计算方式如下

先枚举 i，再枚举 x。相当于先算出所有爷爷节点，再算出所有爷爷的爷爷节点，依此类推.

• pa[x][0]=parent[x]，即父节点。

• pa[x][1]=pa[pa[x][0]][0]，即爷爷节点。

• 一般地，pa[x][i+1]=pa[pa[x][i]][i]。如果 pa[x][i] = -1 则 pa[x][1+1] = -1

这里 i+1至多为 logn 。例如 n = 13 时，log13 = 3，至多需要预处理到第 2^3 个祖先节点。 (当然，你也可以先把树高，或者每个节点的深度求出来，再据此做精细地计算。)

class TreeAncestor {

    private int[][] pa;

    public TreeAncestor(int n, int[] parent) {
        int m = 32 - Integer.numberOfLeadingZeros(n); // n 的二进制长度
        // 预处理出每个节点 x 的第 2^i 个祖先节点，记作 pa[x][i] 
        pa = new int[n][m];
        for(int i = 0; i < n; i++){
            pa[i][0] = parent[i];
        }
        // 先枚举 `i`，再枚举 `x`。相当于先算出所有爷爷节点，再算出所有爷爷的爷爷节点，依此类推
        for(int i = 0; i < m-1; i++){
            for(int x = 0; x < n; x++){
                int p = pa[x][i];
                pa[x][i+1] = p < 0 ? -1 : pa[p][i];
            }
        }
    }
    
    public int getKthAncestor(int node, int k) {
        int m = 32 - Integer.numberOfLeadingZeros(k); // k 的二进制长度
        for(int i = 0; i < m; i++){
            if(((k >> i) & 1) > 0){ // k 的二进制从低到高第 i 位是 1
                node = pa[node][i];
                if(node < 0) break; // 如果node=-1, 说明第k个祖先节点不存在
            }
        }
        return node;
    }
}

2836. 在传球游戏中最大化函数值

困难

给你一个长度为 n 下标从 0 开始的整数数组 receiver 和一个整数 k 。

总共有 n 名玩家，玩家 编号 互不相同，且为 [0, n - 1] 中的整数。这些玩家玩一个传球游戏，receiver[i] 表示编号为 i 的玩家会传球给编号为 receiver[i] 的玩家。玩家可以传球给自己，也就是说 receiver[i] 可能等于 i 。

你需要从 n 名玩家中选择一名玩家作为游戏开始时唯一手中有球的玩家，球会被传 恰好 k 次。

如果选择编号为 x 的玩家作为开始玩家，定义函数 f(x) 表示从编号为 x 的玩家开始，k 次传球内所有接触过球玩家的编号之 和 ，如果有玩家多次触球，则 累加多次 。换句话说， f(x) = x + receiver[x] + receiver[receiver[x]] + ... + receiver(k)[x] 。

你的任务时选择开始玩家 x ，目的是 最大化 f(x) 。

请你返回函数的 最大值 。

注意：receiver 可能含有重复元素。

示例 1：

输入：receiver = [2,0,1], k = 4
输出：6
解释：上表展示了从编号为 x = 2 开始的游戏过程。
从表中可知，f(2) 等于 6 。
6 是能得到最大的函数值。
所以输出为 6 。

示例 2：

输入：receiver = [1,1,1,2,3], k = 3
输出：10
解释：上表展示了从编号为 x = 4 开始的游戏过程。
从表中可知，f(4) 等于 10 。
10 是能得到最大的函数值。
所以输出为 10 。

提示：

• 1 <= receiver.length == n <= 105
• 0 <= receiver[i] <= n - 1
• 1 <= k <= 1010

https://leetcode.cn/circle/discuss/VghzJ4/

我们假设一个点从 $2^i$ 次传球变成 $2^{i+1}$ 次传球，那么我们可以把其动作视为两部分:先传前2次，再传2次。

这样，我们只需要有 $2^i$ 次的终点位置，和每个位置传球 $2^i$ 次的得分，我们就可以得到 $2^{i+1}$ 次传球的终点位置和得分。这种想法叫倍增。

如果我们传球次数不是2的幂次呢?那也没关系，我们可以一个一个2的幂次传，过程中我们只需要记录
结束位置和当前的总和即可。

倍增的好处就在于，我们可以使用很快递增的步长，迅速表示出很长的步长

https://leetcode.cn/problems/maximize-value-of-function-in-a-ball-passing-game/solutions/2413298/shu-shang-bei-zeng-by-endlesscheng-xvsv/

class Solution {
    // 树上倍增, 记录
    // 1. 每个点，顺着 receiver 走 2^i 步之后的结点
    // 2. 从 x 的父节点，到走 2^i 后的节点 【路径上的节点编号之和】 - 倍增
    public long getMaxFunctionValue(List<Integer> receiver, long k) {
        int n = receiver.size();
        int m = 64 - Long.numberOfLeadingZeros(k); // k 的二进制长度
        // pa[x][i] 表示 节点x 顺着 receiver 走 2^i 步之后的结点为 pa[x][i]
        int[][] pa = new int[n][m];
        // sum[x][i] 表示 节点x 顺着 receiver 走 2^i 步之后 【路径上的节点编号之和】 
        long[][] sum = new long[n][m];
        for(int i = 0; i < n; i++){
            pa[i][0] = receiver.get(i);
            sum[i][0] = receiver.get(i);
        }
        for(int i = 0; i < m-1; i++){
            for(int x = 0; x < n; x++){
                int p = pa[x][i];
                pa[x][i+1] = pa[p][i];
                // 合并结点值之和
                // x-> a -> b -> y == (x -> a) + (b -> y) == sum[x][2] = sum[x][1] + sum[i][1]
                sum[x][i+1] = sum[x][i] + sum[p][i]; 
            }
        }
        long ans = 0;
        // 枚举每一个点作为路径起点
        for(int i = 0; i < n; i++){
            long s = i; // 路径之和
            int x = i;
            // 枚举每一个比特位
            for(int j = 0; j < m; j++){
                if(((k >> j) & 1) == 1){ // k 的二进制从低到高第 i 位是 1
                    s += sum[x][j]; 
                    x = pa[x][j]; // x向上跳 2^i 个节点
                }
            }
            ans = Math.max(ans, s);
        }
        return ans;
    }
}

【模板】最近公共祖先(LCA)

https://leetcode.cn/problems/kth-ancestor-of-a-tree-node/solutions/2305895/mo-ban-jiang-jie-shu-shang-bei-zeng-suan-v3rw/

如何计算树上任意两点 $x$ 和 $y$ 的最近公共祖先 $lca$ 呢?

设节点 $i$ 的深度为 $depth[i]$ 。这可以通过一次 $DFS$ 预处理出来

假设 $depth[x]<depth[y]$ (否则交换两点)。我们可以先把更靠下的 $y$ 更新为 $y$ 的第 $depth[y]-depth[x]$ 个祖先节点，这样 $x$ 和 $y$ 就处在同一深度了。

如果此时 $x=y$，那么 $x$ 就是 $\text{lca}$。否则说明 $\text{lca}$ 在更上面，那么就把 $x$ 和 $y$ 一起往上跳。

由于不知道 $\text{lca}$ 的具体位置，只能不断尝试，先尝试大步跳，再尝试小步跳。设 $i=\lfloor {\log }_{2}n\rfloor$ ，循环直到 $i<0$ 。每次循环：

• 如果 $x$ 的第 $2^i$ 个祖先节点不存在，即 $\text{pa}[x][i]=-1$，说明步子迈大了，将 $i$ 减 $1$，继续循环。

• 如果 $x$ 的第 $2^i$ 个祖先节点存在，

  • 且 $\text{pa}[x][i]\ne \text{pa}[y][i]$，说明 $\text{lca}$ 在 $pa[x][i]$ 的上面，那么更新 $x$ 为 $\text{pa}[x][i]$，更新 $y$ 为 $\text{pa}[y][i]$，将 $i$ 减 $1$，继续循环。
  • 否则，若 $\text{pa}[x][i]=\text{pa}[y][i]$，那么 $\text{lca}$ 可能在 $\text{pa}[x][i]$ 下面，由于无法向下跳，只能将 $i$ 减 $1$，继续循环。

上述做法能跳就尽量跳，不会错过任何可以上跳的机会。所以循环结束时，$x$ 与 $\text{lca}$ 只有一步之遥，即 $\text{lca}=\text{pa}[x][0]$。

class TreeAncestor {
    private int[] depth;
    private int[][] pa;

    public TreeAncestor(int[][] edges) {
        int n = edges.length + 1;
        int m = 32 - Integer.numberOfLeadingZeros(n); // n 的二进制长度
        List<Integer> g[] = new ArrayList[n];
        Arrays.setAll(g, e -> new ArrayList<>());
        for (var e : edges) { // 节点编号从 0 开始
            int x = e[0], y = e[1];
            g[x].add(y);
            g[y].add(x);
        }

        depth = new int[n];
        pa = new int[n][m];
        dfs(g, 0, -1);

        for (int i = 0; i < m - 1; i++) {
            for (int x = 0; x < n; x++) {
                int p = pa[x][i];
                pa[x][i + 1] = p < 0 ? -1 : pa[p][i];
            }
        }
    }

    private void dfs(List<Integer>[] g, int x, int fa) {
        pa[x][0] = fa;
        for (int y : g[x]) {
            if (y != fa) {
                depth[y] = depth[x] + 1;
                dfs(g, y, x);
            }
        }
    }

    public int getKthAncestor(int node, int k) {
        for (; k > 0; k &= k - 1)
            node = pa[node][Integer.numberOfTrailingZeros(k)];
        return node;
    }

    public int getLCA(int x, int y) {
        if (depth[x] > depth[y]) {
            int tmp = y;
            y = x;
            x = tmp;
        }
        // 使 y 和 x 在同一深度
        y = getKthAncestor(y, depth[y] - depth[x]);
        if (y == x)
            return x;
        for (int i = pa[x].length - 1; i >= 0; i--) {
            int px = pa[x][i], py = pa[y][i];
            if (px != py) {
                x = px;
                y = py;
            }
        }
        return pa[x][0];
    }
}

补充：
1、 Integer.numberOfLeadingZeros(i)

• 返回无符号整型i的最高非零位前面的n个0的个数，包括符号位。如果i小于0则返回0，等于0则返回32。
• 例：10的二进制为：0000 0000 0000 0000 0000 0000 0000 1010，java的int长度为32位，那么这个方法返回的就是28。

2、Integer.numberOfTrailingZeros(i)

• 返回指定int值的二进制补码二进制表示形式中最低顺序（“最右”）一位之后的零位数目。
• 举例：我们以以下十进制为例。

int dec = 199;

使用Integer.toBinaryString()计算二进制，如下所示-

Integer.toBinaryString(dec);

public class Demo {
   public static void main(String []args) {
      int dec = 199;
      System.out.println("Binary = " + Integer.toBinaryString(dec));
      System.out.println("Count of one bits = " + Integer.bitCount(dec));
      System.out.println("Number of trailing zeros : " + Integer.numberOfTrailingZeros(dec));
   }
}

输出结果

Binary = 11000111
Count of one bits = 5
Number of trailing zeros : 0

2846. 边权重均等查询

困难

现有一棵由 n 个节点组成的无向树，节点按从 0 到 n - 1 编号。给你一个整数 n 和一个长度为 n - 1 的二维整数数组 edges ，其中 edges[i] = [ui, vi, wi] 表示树中存在一条位于节点 ui 和节点 vi 之间、权重为 wi 的边。

另给你一个长度为 m 的二维整数数组 queries ，其中 queries[i] = [ai, bi] 。对于每条查询，请你找出使从 ai 到 bi 路径上每条边的权重相等所需的 最小操作次数 。在一次操作中，你可以选择树上的任意一条边，并将其权重更改为任意值。

注意：

• 查询之间 相互独立 的，这意味着每条新的查询时，树都会回到 初始状态 。
• 从 ai 到 bi的路径是一个由 不同 节点组成的序列，从节点 ai 开始，到节点 bi 结束，且序列中相邻的两个节点在树中共享一条边。

返回一个长度为 m 的数组 answer ，其中 answer[i] 是第 i 条查询的答案。

示例 1：

输入：n = 7, edges = [[0,1,1],[1,2,1],[2,3,1],[3,4,2],[4,5,2],[5,6,2]], queries = [[0,3],[3,6],[2,6],[0,6]]
输出：[0,0,1,3]
解释：第 1 条查询，从节点 0 到节点 3 的路径中的所有边的权重都是 1 。因此，答案为 0 。
第 2 条查询，从节点 3 到节点 6 的路径中的所有边的权重都是 2 。因此，答案为 0 。
第 3 条查询，将边 [2,3] 的权重变更为 2 。在这次操作之后，从节点 2 到节点 6 的路径中的所有边的权重都是 2 。因此，答案为 1 。
第 4 条查询，将边 [0,1]、[1,2]、[2,3] 的权重变更为 2 。在这次操作之后，从节点 0 到节点 6 的路径中的所有边的权重都是 2 。因此，答案为 3 。
对于每条查询 queries[i] ，可以证明 answer[i] 是使从 ai 到 bi 的路径中的所有边的权重相等的最小操作次数。

示例 2：

输入：n = 8, edges = [[1,2,6],[1,3,4],[2,4,6],[2,5,3],[3,6,6],[3,0,8],[7,0,2]], queries = [[4,6],[0,4],[6,5],[7,4]]
输出：[1,2,2,3]
解释：第 1 条查询，将边 [1,3] 的权重变更为 6 。在这次操作之后，从节点 4 到节点 6 的路径中的所有边的权重都是 6 。因此，答案为 1 。
第 2 条查询，将边 [0,3]、[3,1] 的权重变更为 6 。在这次操作之后，从节点 0 到节点 4 的路径中的所有边的权重都是 6 。因此，答案为 2 。
第 3 条查询，将边 [1,3]、[5,2] 的权重变更为 6 。在这次操作之后，从节点 6 到节点 5 的路径中的所有边的权重都是 6 。因此，答案为 2 。
第 4 条查询，将边 [0,7]、[0,3]、[1,3] 的权重变更为 6 。在这次操作之后，从节点 7 到节点 4 的路径中的所有边的权重都是 6 。因此，答案为 3 。
对于每条查询 queries[i] ，可以证明 answer[i] 是使从 ai 到 bi 的路径中的所有边的权重相等的最小操作次数。 

提示：

• 1 <= n <= 104
• edges.length == n - 1
• edges[i].length == 3
• 0 <= ui, vi < n
• 1 <= wi <= 26
• 生成的输入满足 edges 表示一棵有效的树
• 1 <= queries.length == m <= 2 * 104
• queries[i].length == 2
• 0 <= ai, bi < n

LCA应用题

https://leetcode.cn/problems/minimum-edge-weight-equilibrium-queries-in-a-tree/solutions/2424060/lca-mo-ban-by-endlesscheng-j54b/

class Solution {
    /** 关键：提炼问题中需要的信息
    【保留出现次数最多的边，其余的边全部修改】
    1. 从 a 到 b 的路径长度（边数）
        = depth[a] - depth[lca] + (depth[b] - depth[lca]) (lca 为 a 和 b 的最近公共祖先)
        ==> 从 a 到 b 的边数为 depth[a] + depth[b] - 2 * depth[lca]
    2. 从 a 到 b 出现次数最多的边
        1 <= wi <= 26  
        ==> 统计从节点 x 到 x的第 2^i 个祖先节点这条路径上 每种边权的出现次数
     */
    public int[] minOperationsQueries(int n, int[][] edges, int[][] queries) {
        List<int[]>[] g = new ArrayList[n]; // x, y, weight
        Arrays.setAll(g, e -> new ArrayList<>());
        for(int[] e : edges){
            int x = e[0], y = e[1], w = e[2] - 1;
            g[x].add(new int[]{y, w});
            g[y].add(new int[]{x, w});
        }

        int m = 32 - Integer.numberOfLeadingZeros(n); // n 的二进制长度
        int[][] pa = new int[n][m];
        for(int i = 0; i < n; i++){
            Arrays.fill(pa[i], -1);
        }

        // cnt:从节点 x 到 x的第 2^i 个祖先节点这条路径上 每种边权的出现次数
        int[][][] cnt = new int[n][m][26];
        int[] depth = new int[n];
        // 一次dfs处理出 从【节点x 到 x父节点】 的 【边数 + 各边权出现次数 + 深度】
        dfs(0, -1, g, pa, cnt, depth);
        
        // 倍增求 【从节点x到 x^i个祖先节点】 的 各边权出现次数
        for(int i = 0; i < m-1; i++){
            for(int x = 0; x < n; x++){
                int p = pa[x][i]; // p:x 的祖先节点
                if(p != -1){
                    int pp = pa[p][i]; // pp : x祖先的祖先节点
                    pa[x][i+1] = pp;
                    for(int j = 0; j < 26; j++){
                        cnt[x][i+1][j] = cnt[x][i][j] + cnt[p][i][j];
                    }
                }
            }
        }

        int[] ans = new int[queries.length];
        for(int qi = 0; qi < queries.length; qi++){
            int x = queries[qi][0], y = queries[qi][1];

            int pathLen = depth[x] + depth[y];
            int[] cw = new int[26];
            if(depth[x] > depth[y]){ // 目的是让x的深度小于y的深度
                int tmp = x; 
                x = y; 
                y = tmp;
            }

            // 让 y 和 x 在同一深度
            for(int k = depth[y] - depth[x]; k > 0; k &= k-1){
                int i = Integer.numberOfTrailingZeros(k);
                int p = pa[y][i];
                for(int j = 0; j < 26; j++){
                    cw[j] += cnt[y][i][j];
                }
                y = p;
            }

            // 求 x 和 y 上的lca节点
            if(y != x){ // 从大到小尝试跳（lca模板）
                for(int i = m-1; i >= 0; i--){
                    int px = pa[x][i], py = pa[y][i];
                    if(px != py){ // 说明 lca节点在pa节点上面，更新x和y
                        for(int j = 0; j < 26; j++)
                            cw[j] += cnt[x][i][j] + cnt[y][i][j];
                        x = px;
                        y = py; // x 和 y 同时上跳 2^i 步
                    }
                }
                for(int j = 0; j < 26; j++)
                    cw[j] += cnt[x][0][j] + cnt[y][0][j];
                x = pa[x][0]; // 循环结束，x和lca节点只有一步之遥，即lca节点是x的父节点
            }

            int lca = x;
            pathLen -= depth[lca] * 2;
            int maxcw = 0; // 边权最大出现次数
            for(int i = 0; i < 26; i++){
                maxcw = Math.max(maxcw, cw[i]);
            }
            ans[qi] = pathLen - maxcw;
        }
        return ans;
    }

    public void dfs(int x, int fa, List<int[]>[] g, int[][] pa, int[][][] cnt, int[] depth){
        pa[x][0] = fa;
        for(int[] e : g[x]){
            int y = e[0], w = e[1];
            if(y != fa){
                cnt[y][0][w] = 1; // 表示 从 y 到 y的第2^0节点(x节点) 有一个边权为w的边
                depth[y] = depth[x] + 1;
                dfs(y, x, g, pa, cnt, depth);
            }
        }
    }
}

练习

1.树的直径相关问题

687. 最长同值路径

难度中等762

给定一个二叉树的 root ，返回 最长的路径的长度 ，这个路径中的 每个节点具有相同值 。 这条路径可以经过也可以不经过根节点。

两个节点之间的路径长度 由它们之间的边数表示。

示例 1:

输入：root = [5,4,5,1,1,5]
输出：2

示例 2:

输入：root = [1,4,5,4,4,5]
输出：2

提示:

• 树的节点数的范围是 [0, 104]
• -1000 <= Node.val <= 1000
• 树的深度将不超过 1000

class Solution {
    int res = 0;
    public int longestUnivaluePath(TreeNode root) {
        dfs(root);
        return res;
    }

    public int dfs(TreeNode node){
        if(node == null) 
            return -1; // 下面 +1 后，对于叶子节点就刚好是 0
        int leftlen = dfs(node.left) + 1; // 左子树最大链长+1
        int rightlen = dfs(node.right) + 1; // 右子树最大链长+1

        // 如果当前节点的值与左/右子树的值不同，链长可视作0
        if(node.left != null && node.left.val != node.val) leftlen = 0;
        if(node.right != null && node.right.val != node.val) rightlen = 0;
        
        res = Math.max(res, leftlen + rightlen); // 两条链拼成路径
        return Math.max(leftlen, rightlen); // 当前子树最大链长
    }
}

1617. 统计子树中城市之间最大距离

难度困难149

给你 n 个城市，编号为从 1 到 n 。同时给你一个大小为 n-1 的数组 edges ，其中 edges[i] = [ui, vi] 表示城市 ui 和 vi 之间有一条双向边。题目保证任意城市之间只有唯一的一条路径。换句话说，所有城市形成了一棵 树 。

一棵 子树 是城市的一个子集，且子集中任意城市之间可以通过子集中的其他城市和边到达。两个子树被认为不一样的条件是至少有一个城市在其中一棵子树中存在，但在另一棵子树中不存在。

对于 d 从 1 到 n-1 ，请你找到城市间 最大距离 恰好为 d 的所有子树数目。

请你返回一个大小为 n-1 的数组，其中第 d 个元素（下标从 1 开始）是城市间 最大距离 恰好等于 d 的子树数目。

请注意，两个城市间距离定义为它们之间需要经过的边的数目。

示例 1：

输入：n = 4, edges = [[1,2],[2,3],[2,4]]
输出：[3,4,0]
解释：
子树 {1,2}, {2,3} 和 {2,4} 最大距离都是 1 。
子树 {1,2,3}, {1,2,4}, {2,3,4} 和 {1,2,3,4} 最大距离都为 2 。
不存在城市间最大距离为 3 的子树。

示例 2：

输入：n = 2, edges = [[1,2]]
输出：[1]

示例 3：

输入：n = 3, edges = [[1,2],[2,3]]
输出：[2,1]

提示：

• 2 <= n <= 15
• edges.length == n-1
• edges[i].length == 2
• 1 <= ui, vi <= n
• 题目保证 (ui, vi) 所表示的边互不相同。

本题结合了 78 题和 1245 题：枚举城市的子集（子树），求这棵子树的直径。

需要注意的是，枚举的子集不一定是一棵树，可能是森林（多棵树，多个连通块）。我们可以在计算树形 DP 的同时去统计访问过的点，看看是否与子集相等，只有相等才是一棵树。

class Solution {
    int[] res;
    boolean[] inSet, vis;
    int n, diameter;
    List<Integer>[] g;
    public int[] countSubgraphsForEachDiameter(int n, int[][] edges) {
        res = new int[n-1];
        g = new ArrayList[n];
        inSet = new boolean[n];
        this.n = n;
        Arrays.setAll(g, e -> new ArrayList<>());
        for(int[] e : edges){
            int x = e[0] - 1, y = e[1] - 1;
            g[x].add(y);
            g[y].add(x);
        }
        f(0); // 回溯：枚举所有子集的可能性
        return res;
    }
    // 枚举所有子树的可能性（子集型回溯）
    public void f(int i){
        if(i == n){
            // 枚举的子集不一定是一棵树，可能是森林
            for(int v = 0; v < n; v++){
                if(inSet[v]){
                    vis = new boolean[n];
                    diameter = 0;
                    dfs(v);
                    break;
                }
            }
            if(diameter > 0 && Arrays.equals(vis, inSet)){
                ++res[diameter-1];
            }
            return;
        }
        f(i+1); // 不选城市i
        // 选城市i
        inSet[i] = true;
        f(i+1);
        inSet[i] = false;
    }

    // 求树的直径
    public int dfs(int x){
        vis[x] = true;
        int maxLen = 0;
        for(int y : g[x]){
            if(!vis[y] && inSet[y]){
                int ml = dfs(y) + 1;
                diameter = Math.max(diameter, maxLen + ml);
                maxLen = Math.max(maxLen, ml);
            }
        }
        return maxLen;
    }
}

2538. 最大价值和与最小价值和的差值

难度困难33

给你一个 n 个节点的无向无根图，节点编号为 0 到 n - 1 。给你一个整数 n 和一个长度为 n - 1 的二维整数数组 edges ，其中 edges[i] = [ai, bi] 表示树中节点 ai 和 bi 之间有一条边。

每个节点都有一个价值。给你一个整数数组 price ，其中 price[i] 是第 i 个节点的价值。

一条路径的 价值和 是这条路径上所有节点的价值之和。

你可以选择树中任意一个节点作为根节点 root 。选择 root 为根的 开销 是以 root 为起点的所有路径中，价值和 最大的一条路径与最小的一条路径的差值。

请你返回所有节点作为根节点的选择中，最大 的 开销 为多少。

示例 1：

输入：n = 6, edges = [[0,1],[1,2],[1,3],[3,4],[3,5]], price = [9,8,7,6,10,5]
输出：24
解释：上图展示了以节点 2 为根的树。左图（红色的节点）是最大价值和路径，右图（蓝色的节点）是最小价值和路径。
- 第一条路径节点为 [2,1,3,4]：价值为 [7,8,6,10] ，价值和为 31 。
- 第二条路径节点为 [2] ，价值为 [7] 。
最大路径和与最小路径和的差值为 24 。24 是所有方案中的最大开销。

示例 2：

输入：n = 3, edges = [[0,1],[1,2]], price = [1,1,1]
输出：2
解释：上图展示了以节点 0 为根的树。左图（红色的节点）是最大价值和路径，右图（蓝色的节点）是最小价值和路径。
- 第一条路径包含节点 [0,1,2]：价值为 [1,1,1] ，价值和为 3 。
- 第二条路径节点为 [0] ，价值为 [1] 。
最大路径和与最小路径和的差值为 2 。2 是所有方案中的最大开销。

提示：

• 1 <= n <= 105
• edges.length == n - 1
• 0 <= ai, bi <= n - 1
• edges 表示一棵符合题面要求的树。
• price.length == n
• 1 <= price[i] <= 105

题解：0x3f：https://leetcode.cn/problems/difference-between-maximum-and-minimum-price-sum/solution/by-endlesscheng-5l70/

1、由于价值都是正数，因此价值和最小的一条路径一定只有一个点。

2、根据提示 1，「价值和最大的一条路径与最小的一条路径的差值」等价于「去掉路径的一个端点」。

3、由于价值都是正数，一条路径能延长就尽量延长，这样路径和就越大，那么最优是延长到叶子。根据提示 2，问题转换成去掉一个叶子后的最大路径和（这里的叶子严格来说是度为 1 的点，因为根的度数也可能是 1）。

4、最大路径和是一个经典树形 DP 问题，类似「树的直径」。由于我们需要去掉一个叶子，那么可以让子树返回两个值：

• 带叶子的最大路径和；

• 不带叶子的最大路径和。

对于当前节点，它有多颗子树，我们一颗颗 DFS，假设当前 DFS 完了其中一颗子树，它返回了「当前带叶子的路径和」和「当前不带叶子的路径和」，那么答案有两种情况：

• 前面最大带叶子的路径和 + 当前不带叶子的路径和；

• 前面最大不带叶子的路径和 + 当前带叶子的路径和；

然后更新「最大带叶子的路径和」和「最大不带叶子的路径和」。

最后返回「最大带叶子的路径和」和「最大不带叶子的路径和」，用来供父节点计算。

class Solution {
    List<Integer>[] g;
    int n;
    long res;
    int[] price;
    public long maxOutput(int n, int[][] edges, int[] price) {
        this.n = n;
        g = new ArrayList[n];
        Arrays.setAll(g, e -> new ArrayList<>());
        for(int[] e : edges){
            int x = e[0], y = e[1];
            g[x].add(y);
            g[y].add(x);
        }
        this.price = price;
        dfs(0, -1);
        return res;
    }

    // 返回带叶子的最大路径和，不带叶子的最大路径和
    public long[] dfs(int x, int fa){
        // s1 带叶子的最大路径和 ； s2 不带叶子的最大路径和
        long p = price[x], maxS1 = p, maxS2 = 0;
        for(int y : g[x]){
            if(y != fa){
                long[] result = dfs(y, x);
                long s1 = result[0], s2 = result[1];
                // 前面最大带叶子的路径和 + 当前不带叶子的路径和
                // 前面最大不带叶子的路径和 + 当前带叶子的路径和
                res = Math.max(res, Math.max(maxS1 + s2, maxS2 + s1));
                // 这里加上 p 是因为 x 必然不是叶子
                maxS1 = Math.max(maxS1, s1 + p);
                maxS2 = Math.max(maxS2, s2 + p);
            }
        }
        return new long[]{maxS1, maxS2};
    }
}

2.树上最大独立集练习题

P1352 没有上司的舞会

题目描述

某大学有 $n$ 个职员，编号为 $1\dots n$。

他们之间有从属关系，也就是说他们的关系就像一棵以校长为根的树，父结点就是子结点的直接上司。

现在有个周年庆宴会，宴会每邀请来一个职员都会增加一定的快乐指数 $r_i$，但是呢，如果某个职员的直接上司来参加舞会了，那么这个职员就无论如何也不肯来参加舞会了。

所以，请你编程计算，邀请哪些职员可以使快乐指数最大，求最大的快乐指数。

输入格式

输入的第一行是一个整数 $n$。

第 $2$ 到第 $(n+1)$ 行，每行一个整数，第 $(i+1)$ 行的整数表示 $i$ 号职员的快乐指数 $r_i$。

第 $(n+2)$ 到第 $2n$ 行，每行输入一对整数 $l,k$，代表 $k$ 是 $l$ 的直接上司。

输出格式

输出一行一个整数代表最大的快乐指数。

样例 #1

样例输入 #1

7
1
1
1
1
1
1
1
1 3
2 3
6 4
7 4
4 5
3 5

样例输出 #1

5

数据规模与约定

对于 $100\%$ 的数据，保证 $1\le n\le 6\times 10^3$，$-128\le r_i\le 127$，$1\le l,k\le n$，且给出的关系一定是一棵树。

public class test {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        int n = Integer.valueOf(br.readLine());
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = Integer.valueOf(br.readLine());
        }
        // 入度 + 1，出度 - 1，根据最大入度找根节点
        int[] degree = new int[n];
        List<Integer>[] g = new ArrayList[n];
        Arrays.setAll(g, e -> new ArrayList<>());
        for (int i = 0; i < n - 1; i++) {
            String[] strs = br.readLine().split(" ");
            int x = Integer.valueOf(strs[0]) - 1;
            int y = Integer.valueOf(strs[1]) - 1;
            g[y].add(x);
            degree[y] += 1;
            degree[x] -= 1;
        }
        int fa = 0;
        for (int i = 0; i < n; i++) {
            if (degree[i] > degree[fa])
                fa = i;
        }
        int[] res = dfs(fa, g, nums);
        out.println(Math.max(res[0], res[1]));
        out.flush();
    }

    // res[0] : 选 = 左不选 + 右不选 + 当前节点值
    // res[1] : 不选 = max(左选,左不选) + max(右选,右不选)
    public static int[] dfs(int i, List<Integer>[] g, int[] nums) {
        if (g[i].size() == 0)
            return new int[] { 1, 0 };
        int[] res = new int[2];
        for (int y : g[i]) {
            int[] child = dfs(y, g, nums);
            res[0] += child[1];
            res[1] += Math.max(child[0], child[1]);
        }
        res[0] += nums[i];
        return res;
    }
}

1377. T 秒后青蛙的位置

难度困难103

给你一棵由 n 个顶点组成的无向树，顶点编号从 1 到 n。青蛙从 顶点 1 开始起跳。规则如下：

• 在一秒内，青蛙从它所在的当前顶点跳到另一个 未访问 过的顶点（如果它们直接相连）。
• 青蛙无法跳回已经访问过的顶点。
• 如果青蛙可以跳到多个不同顶点，那么它跳到其中任意一个顶点上的机率都相同。
• 如果青蛙不能跳到任何未访问过的顶点上，那么它每次跳跃都会停留在原地。

无向树的边用数组 edges 描述，其中 edges[i] = [ai, bi] 意味着存在一条直接连通 ai 和 bi 两个顶点的边。

返回青蛙在 t 秒后位于目标顶点 target 上的概率。与实际答案相差不超过 10-5 的结果将被视为正确答案。

示例 1：

输入：n = 7, edges = [[1,2],[1,3],[1,7],[2,4],[2,6],[3,5]], t = 2, target = 4
输出：0.16666666666666666 
解释：上图显示了青蛙的跳跃路径。青蛙从顶点 1 起跳，第 1 秒 有 1/3 的概率跳到顶点 2 ，然后第 2 秒 有 1/2 的概率跳到顶点 4，因此青蛙在 2 秒后位于顶点 4 的概率是 1/3 * 1/2 = 1/6 = 0.16666666666666666 。 

示例 2：

输入：n = 7, edges = [[1,2],[1,3],[1,7],[2,4],[2,6],[3,5]], t = 1, target = 7
输出：0.3333333333333333
解释：上图显示了青蛙的跳跃路径。青蛙从顶点 1 起跳，有 1/3 = 0.3333333333333333 的概率能够 1 秒 后跳到顶点 7 。 

提示：

• 1 <= n <= 100
• edges.length == n - 1
• edges[i].length == 2
• 1 <= ai, bi <= n
• 1 <= t <= 50
• 1 <= target <= n

https://blog.csdn.net/qq_42958831/article/details/130839438

https://leetcode.cn/problems/frog-position-after-t-seconds/solution/dfs-ji-yi-ci-you-qu-de-hack-by-endlessch-jtsr/

既然答案是由若干分子为 1 的分数相乘得到，那么干脆只把分母相乘，最后再计算一下倒数，就可以避免因浮点乘法导致的精度丢失了。另外，整数的计算效率通常比浮点数的高。

• 自顶向下是一边[递]，一边把儿子个数 c 乘起来，如果能在第 t 秒到达 target，或者小于t 秒到达 target 且 target 是叶子节点(此时每次跳跃都会停留在原地) ，那么就记录答案为乘积的倒数，同时返回一个布尔值表示递归结束
• 自底向上的思路是类似的，找到 target 后，在[归]的过程中做乘法。 个人更喜欢这种写法，因为只在找到 target 之后才做乘法，而自顶向下即使在不含 target 的子树中搜索，也会盲目地做乘法。

技巧：
可以把节点 1 添加一个 0 号邻居，从而避免判断当前节点为根节点1，也避免了特判 n = 1的情况

此外，DFS 中的时间不是从 0 开始增加到 t，而是从 leftT = t 开始减小到 0，这样代码中只需和 0 比较，无需和 t 比较，从而减少一个DFS 之外变量的引入。

方法一：自顶向下

class Solution {
    List<Integer>[] g;
    double ans = 0.0;
    int target;
    public double frogPosition(int n, int[][] edges, int t, int target) {
        this.target = target;
        g = new ArrayList[n+1];
        Arrays.setAll(g, e -> new ArrayList<>());
        g[1].add(0);
        for(int[] e : edges){
            int x = e[0], y = e[1];
            g[x].add(y);
            g[y].add(x);
        }
        dfs(1, 0, t, 1);
        return ans;
    }

    public boolean dfs(int x, int fa, int left_time, long prod){
        // t 秒后必须在 target（恰好到达，或者 target 是叶子停在原地）
        if(x == target && (left_time == 0 || g[x].size() == 1)){
            ans = 1.0 / prod;
            return true;
        }
        if(x == target || left_time == 0) return false;
        for(int y : g[x]){ // 遍历 x 的儿子 y
            if(y != fa && dfs(y, x, left_time-1, prod * (g[x].size() - 1)))
                return true; // 找到 target 就不再递归了
        }
        return false; // 未找到target
    }
}

方法二：自底向上

class Solution {
    List<Integer>[] g;
    int target;
    public double frogPosition(int n, int[][] edges, int t, int target) {
        this.target = target;
        g = new ArrayList[n+1];
        Arrays.setAll(g, e -> new ArrayList<>());
        g[1].add(0);
        for(int[] e : edges){
            int x = e[0], y = e[1];
            g[x].add(y);
            g[y].add(x);
        }
        long prod = dfs(1, 0, t);
        return prod != 0 ? 1.0 / prod : 0;
    }

    public long dfs(int x, int fa, int left_time){
        if(left_time == 0)
            return x == target ? 1 : 0;
        if(x == target) 
            return g[x].size() == 1 ? 1 : 0;
        for(int y : g[x]){
            if(y != fa){
                long prod = dfs(y, x, left_time-1); // 寻找 target
                if(prod != 0){
                    return prod * (g[x].size() - 1); // 乘上儿子个数，并直接返回
                }
            }
        }
        return 0; // 未找到target
    }
}

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

难度困难29

现有一棵无向、无根的树，树中有 n 个节点，按从 0 到 n - 1 编号。给你一个整数 n 和一个长度为 n - 1 的二维整数数组 edges ，其中 edges[i] = [ai, bi] 表示树中节点 ai 和 bi 之间存在一条边。

每个节点都关联一个价格。给你一个整数数组 price ，其中 price[i] 是第 i 个节点的价格。

给定路径的 价格总和 是该路径上所有节点的价格之和。

另给你一个二维整数数组 trips ，其中 trips[i] = [starti, endi] 表示您从节点 starti 开始第 i 次旅行，并通过任何你喜欢的路径前往节点 endi 。

在执行第一次旅行之前，你可以选择一些 非相邻节点 并将价格减半。

返回执行所有旅行的最小价格总和。

示例 1：

输入：n = 4, edges = [[0,1],[1,2],[1,3]], price = [2,2,10,6], trips = [[0,3],[2,1],[2,3]]
输出：23
解释：
上图表示将节点 2 视为根之后的树结构。第一个图表示初始树，第二个图表示选择节点 0 、2 和 3 并使其价格减半后的树。
第 1 次旅行，选择路径 [0,1,3] 。路径的价格总和为 1 + 2 + 3 = 6 。
第 2 次旅行，选择路径 [2,1] 。路径的价格总和为 2 + 5 = 7 。
第 3 次旅行，选择路径 [2,1,3] 。路径的价格总和为 5 + 2 + 3 = 10 。
所有旅行的价格总和为 6 + 7 + 10 = 23 。可以证明，23 是可以实现的最小答案。

示例 2：

输入：n = 2, edges = [[0,1]], price = [2,2], trips = [[0,0]]
输出：1
解释：
上图表示将节点 0 视为根之后的树结构。第一个图表示初始树，第二个图表示选择节点 0 并使其价格减半后的树。 
第 1 次旅行，选择路径 [0] 。路径的价格总和为 1 。 
所有旅行的价格总和为 1 。可以证明，1 是可以实现的最小答案。

提示：文章来源地址https://www.toymoban.com/news/detail-761386.html

• 1 <= n <= 50
• edges.length == n - 1
• 0 <= ai, bi <= n - 1
• edges 表示一棵有效的树
• price.length == n
• price[i] 是一个偶数
• 1 <= price[i] <= 1000
• 1 <= trips.length <= 100
• 0 <= starti, endi <= n - 1

class Solution {
    // 1. 计算每个点经过的次数 cnt（贡献法思想：计算每个点对答案能贡献多少）
    // 2. 写一个树形DP求答案
    private List<Integer>[] g;
    private int[] price, cnt;
    private int end;

    public int minimumTotalPrice(int n, int[][] edges, int[] price, int[][] trips) {
        g = new ArrayList[n];
        Arrays.setAll(g, e -> new ArrayList<>());
        for(int[] e : edges){
            int x = e[0], y = e[1];
            g[x].add(y);
            g[y].add(x); // 建树
        }
        this.price = price;

        // 1. 计算每个点经过的次数 cnt
        cnt = new int[n];
        for(int[] t : trips){
            end = t[1];
            path(t[0], -1);
        }
        // 2. 写一个树形DP求答案
        // 随便选一个点出发进行DP就可以了
        // 为什么？题目的描述与根节点无关
        int[] p = dfs(0, -1); 
        return Math.min(p[0], p[1]);

    }
    // 寻找路径，找到终点就返回True（注意树只有唯一的一条简单路径）
    // 寻找路径的同时标记源点到终点所有的点 +1
    private boolean path(int x, int fa) {
        if(x == end){ // 到达终点
            cnt[x]++; // 统计从 start 到 end 的路径上的点经过了多少次
            return true;
        }
        for(int y : g[x]){
            if(y != fa && path(y,x)){
                cnt[x]++; // 统计从 start 到 end 的路径上的点经过了多少次
                return true; // 找到终点
            }
        }
        return false; // 未找到终点
    }

    private int[] dfs(int x, int fa){
        int notHalve = price[x] * cnt[x]; // x 不变
        int halve = notHalve / 2; // x 减半
        for(int y : g[x]){
            if(y != fa){
                int[] p = dfs(y, x); // 计算 y 不变/减半的最小价值总和
                // x没有减半的话，y既可以减半，也可以不减半，取这两种情况的最小值
                notHalve += Math.min(p[0], p[1]);
                halve += p[0]; // x 减半，那么 y 只能不变
            }
        }
        return new int[]{notHalve, halve};
    }
}

到了这里，关于11.动态规划：树形DP问题、树上最大独立集、树上最小支配集、换根DP、树上倍增（LCA）【灵神基础精讲】的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！