代码如诗

100108. 收集所有金币可获得的最大积分

节点 0 处现有一棵由 n 个节点组成的无向树，节点编号从 0 到 n - 1 。给你一个长度为 n - 1 的二维 整数 数组 edges ，其中 edges[i] = [ai, bi] 表示在树上的节点 ai 和 bi 之间存在一条边。另给你一个下标从 0 开始、长度为 n 的数组 coins 和一个整数 k ，其中 coins[i] 表示节点 i 处的金币数量。

从根节点开始，你必须收集所有金币。要想收集节点上的金币，必须先收集该节点的祖先节点上的金币。

节点 i 上的金币可以用下述方法之一进行收集：

• 收集所有金币，得到共计 coins[i] - k 点积分。如果 coins[i] - k 是负数，你将会失去 abs(coins[i] - k) 点积分。

• 收集所有金币，得到共计 floor(coins[i] / 2) 点积分。如果采用这种方法，节点 i 子树中所有节点 j 的金币数 coins[j] 将会减少至 floor(coins[j] / 2) 。

返回收集 所有 树节点的金币之后可以获得的最大积分。

示例 1：

```txt

输入：edges = [[0,1],[1,2],[2,3]], coins = [10,10,3,3], k = 5

输出：11

解释：

使用第一种方法收集节点 0 上的所有金币。总积分 = 10 - 5 = 5 。

使用第一种方法收集节点 1 上的所有金币。总积分 = 5 + (10 - 5) = 10 。

使用第二种方法收集节点 2 上的所有金币。所以节点 3 上的金币将会变为 floor(3 / 2) = 1 ，总积分 = 10 + floor(3 / 2) = 11 。

使用第二种方法收集节点 3 上的所有金币。总积分 = 11 + floor(1 / 2) = 11.

可以证明收集所有节点上的金币能获得的最大积分是 11 。

```

示例 2：

```txt

输入：edges = [[0,1],[0,2]], coins = [8,4,4], k = 0

输出：16

解释：

使用第一种方法收集所有节点上的金币，因此，总积分 = (8 - 0) + (4 - 0) + (4 - 0) = 16 。

```

提示：

• n == coins.length

• 2 <= n <= 10^5

• 0 <= coins[i] <= 10^4

• edges.length == n - 1

• 0 <= edges[i][0], edges[i][1] < n

• 0 <= k <= 10^4

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

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

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

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

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

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

示例 1：

```txt

输入：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：

```txt

输入：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 <= 10^5

• edges.length == n - 1

• 0 <= ai, bi <= n - 1

• edges 表示一棵符合题面要求的树。

• price.length == n

• 1 <= price[i] <= 10^5

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

现有一棵无向、无根的树，树中有 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：

```txt

输入：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：

```txt

输入：n = 2, edges = [[0,1]], price = [2,2], trips = [[0,0]]

输出：1

解释：

上图表示将节点 0 视为根之后的树结构。第一个图表示初始树，第二个图表示选择节点 0 并使其价格减半后的树。

第 1 次旅行，选择路径 [0] 。路径的价格总和为 1 。

所有旅行的价格总和为 1 。可以证明，1 是可以实现的最小答案。

```

提示：

• 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

2246. 相邻字符不同的最长路径

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

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

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

示例 1：

```txt

输入：parent = [-1,0,0,1,1,2], s = "abacbe"

输出：3

解释：任意一对相邻节点字符都不同的最长路径是：0 -> 1 -> 3 。该路径的长度是 3 ，所以返回 3 。

可以证明不存在满足上述条件且比 3 更长的路径。

```

示例 2：

```txt

输入：parent = [-1,0,0,0], s = "aabc"

输出：3

解释：任意一对相邻节点字符都不同的最长路径是：2 -> 0 -> 3 。该路径的长度为 3 ，所以返回 3 。

```

提示：

• n == parent.length == s.length

• 1 <= n <= 10^5

• 对所有 i >= 1 ，0 <= parent[i] <= n - 1 均成立

• parent[0] == -1

• parent 表示一棵有效的树

• s 仅由小写英文字母组成

2458. 移除子树后的二叉树高度

给你一棵 二叉树 的根节点 root ，树中有 n 个节点。每个节点都可以被分配一个从 1 到 n 且互不相同的值。另给你一个长度为 m 的数组 queries 。

你必须在树上执行 m 个 独立 的查询，其中第 i 个查询你需要执行以下操作：

• 从树中 移除 以 queries[i] 的值作为根节点的子树。题目所用测试用例保证 queries[i] 不 等于根节点的值。

返回一个长度为 m 的数组 answer ，其中 answer[i] 是执行第 i 个查询后树的高度。

注意：

• 查询之间是独立的，所以在每个查询执行后，树会回到其 初始 状态。

• 树的高度是从根到树中某个节点的 最长简单路径中的边数 。

示例 1：

```txt

输入：root = [1,3,4,2,null,6,5,null,null,null,null,null,7], queries = [4]

输出：[2]

解释：上图展示了从树中移除以 4 为根节点的子树。

树的高度是 2（路径为 1 -> 3 -> 2）。

```

示例 2：

```txt

输入：root = [5,8,9,2,1,3,7,4,6], queries = [3,2,4,8]

输出：[3,2,3,2]

解释：执行下述查询：

• 移除以 3 为根节点的子树。树的高度变为 3（路径为 5 -> 8 -> 2 -> 4）。

• 移除以 2 为根节点的子树。树的高度变为 2（路径为 5 -> 8 -> 1）。

• 移除以 4 为根节点的子树。树的高度变为 3（路径为 5 -> 8 -> 2 -> 6）。

• 移除以 8 为根节点的子树。树的高度变为 2（路径为 5 -> 9 -> 3）。

```

提示：

• 树中节点的数目是 n

• 2 <= n <= 10^5

• 1 <= Node.val <= n

• 树中的所有值 互不相同

• m == queries.length

• 1 <= m <= min(n, 10^4)

• 1 <= queries[i] <= n

• queries[i] != root.val

2581. 统计可能的树根数目

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：

```txt

输入：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：

```txt

输入：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 <= 10^5

• 1 <= guesses.length <= 10^5

• 0 <= ai, bi, uj, vj <= n - 1

• ai != bi

• uj != vj

• edges 表示一棵有效的树。

• guesses[j] 是树中的一条边。

• guesses 是唯一的。

• 0 <= k <= guesses.length

1494. 并行课程 II

给你一个整数 n 表示某所大学里课程的数目，编号为 1 到 n ，数组 relations 中， relations[i] = [xi, yi]  表示一个先修课的关系，也就是课程 xi 必须在课程 yi 之前上。同时你还有一个整数 k 。

在一个学期中，你 最多 可以同时上 k 门课，前提是这些课的先修课在之前的学期里已经上过了。

请你返回上完所有课最少需要多少个学期。题目保证一定存在一种上完所有课的方式。

示例 1：

```txt

输入：n = 4, relations = [[2,1],[3,1],[1,4]], k = 2

输出：3

解释：上图展示了题目输入的图。在第一个学期中，我们可以上课程 2 和课程 3 。然后第二个学期上课程 1 ，第三个学期上课程 4 。

```

示例 2：

```txt

输入：n = 5, relations = [[2,1],[3,1],[4,1],[1,5]], k = 2

输出：4

解释：上图展示了题目输入的图。一个最优方案是：第一学期上课程 2 和 3，第二学期上课程 4 ，第三学期上课程 1 ，第四学期上课程 5 。

```

示例 3：

```txt

输入：n = 11, relations = [], k = 2

输出：6

```

提示：

• 1 <= n <= 15

• 1 <= k <= n

• 0 <= relations.length <= n * (n-1) / 2

• relations[i].length == 2

• 1 <= xi, yi <= n

• xi != yi

• 所有先修关系都是不同的，也就是说 relations[i] != relations[j] 。

• 题目输入的图是个有向无环图。