fork()==0世界线变动

810. 黑板异或游戏

黑板上写着一个非负整数数组 nums[i] 。

Alice 和 Bob 轮流从黑板上擦掉一个数字，Alice 先手。如果擦除一个数字后，剩余的所有数字按位异或运算得出的结果等于 0 的话，当前玩家游戏失败。 另外，如果只剩一个数字，按位异或运算得到它本身；如果无数字剩余，按位异或运算结果为 0。

并且，轮到某个玩家时，如果当前黑板上所有数字按位异或运算结果等于 0 ，这个玩家获胜。

假设两个玩家每步都使用最优解，当且仅当 Alice 获胜时返回 true。

示例 1：

```txt

输入: nums = [1,1,2]

输出: false

解释:

Alice 有两个选择: 擦掉数字 1 或 2。

如果擦掉 1, 数组变成 [1, 2]。剩余数字按位异或得到 1 XOR 2 = 3。那么 Bob 可以擦掉任意数字，因为 Alice 会成为擦掉最后一个数字的人，她总是会输。

如果 Alice 擦掉 2，那么数组变成[1, 1]。剩余数字按位异或得到 1 XOR 1 = 0。Alice 仍然会输掉游戏。

```

示例 2:

```txt

输入: nums = [0,1]

输出: true

```

示例 3:

```txt

输入: nums = [1,2,3]

输出: true

```

提示：

• 1 <= nums.length <= 1000

• 0 <= nums[i] < 2^16

1092. 最短公共超序列

给你两个字符串 str1 和 str2，返回同时以 str1 和 str2 作为 子序列 的最短字符串。如果答案不止一个，则可以返回满足条件的 任意一个 答案。

如果从字符串 t 中删除一些字符（也可能不删除），可以得到字符串 s ，那么 s 就是 t 的一个子序列。

示例 1：

```txt

输入：str1 = "abac", str2 = "cab"

输出："cabac"

解释：

str1 = "abac" 是 "cabac" 的一个子串，因为我们可以删去 "cabac" 的第一个 "c"得到 "abac"。

str2 = "cab" 是 "cabac" 的一个子串，因为我们可以删去 "cabac" 末尾的 "ac" 得到 "cab"。

最终我们给出的答案是满足上述属性的最短字符串。

```

示例 2：

```txt

输入：str1 = "aaaaaaaa", str2 = "aaaaaaaa"

输出："aaaaaaaa"

```

提示：

• 1 <= str1.length, str2.length <= 1000

• str1 和 str2 都由小写英文字母组成。

1039. 多边形三角剖分的最低得分

你有一个凸的 n 边形，其每个顶点都有一个整数值。给定一个整数数组 values ，其中 values[i] 是第 i 个顶点的值（即 顺时针顺序 ）。

假设将多边形 剖分 为 n - 2 个三角形。对于每个三角形，该三角形的值是顶点标记的乘积，三角剖分的分数是进行三角剖分后所有 n - 2 个三角形的值之和。

返回 多边形进行三角剖分后可以得到的最低分 。

示例 1：

```txt

输入：values = [1,2,3]

输出：6

解释：多边形已经三角化，唯一三角形的分数为 6。

```

示例 2：

```txt

输入：values = [3,7,4,5]

输出：144

解释：有两种三角剖分，可能得分分别为：375 + 457 = 245，或 345 + 347 = 144。最低分数为 144。

```

示例 3：

```txt

输入：values = [1,3,1,4,1,5]

输出：13

解释：最低分数三角剖分的得分情况为 113 + 114 + 115 + 111 = 13。

```

提示：

• n == values.length

• 3 <= n <= 50

• 1 <= values[i] <= 100

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：

```txt

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

```txt

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

• edges.length == n - 1

• edges[i].length == 2

• 0 <= ui == edges[i][0] < n

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

• ui != vi

• 输入保证如果边是双向边，可以得到一棵树。

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

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

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