fork()==0世界线变动

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

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

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

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

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

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

示例 1：

```txt

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

```txt

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

输出：[1]

```

示例 3：

```txt

输入：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) 所表示的边互不相同。

6353. 网格图中最少访问的格子数

给你一个下标从 0 开始的 m x n 整数矩阵 grid 。你一开始的位置在 左上角 格子 (0, 0) 。

当你在格子 (i, j) 的时候，你可以移动到以下格子之一：

• 满足 j < k <= grid[i][j] + j 的格子 (i, k) （向右移动），或者

• 满足 i < k <= grid[i][j] + i 的格子 (k, j) （向下移动）。

请你返回到达 右下角 格子 (m - 1, n - 1) 需要经过的最少移动格子数，如果无法到达右下角格子，请你返回 -1 。

示例 1：

```txt

输入：grid = [[3,4,2,1],[4,2,3,1],[2,1,0,0],[2,4,0,0]]

输出：4

解释：上图展示了到达右下角格子经过的 4 个格子。

```

示例 2：

```txt

输入：grid = [[3,4,2,1],[4,2,1,1],[2,1,1,0],[3,4,1,0]]

输出：3

解释：上图展示了到达右下角格子经过的 3 个格子。

```

示例 3：

```txt

输入：grid = [[2,1,0],[1,0,0]]

输出：-1

解释：无法到达右下角格子。

```

提示：

• m == grid.length

• n == grid[i].length

• 1 <= m, n <= 10^5

• 1 <= m * n <= 10^5

• 0 <= grid[i][j] < m * n

• grid[m - 1][n - 1] == 0

864. 获取所有钥匙的最短路径

给定一个二维网格 grid ，其中：

• '.' 代表一个空房间

• '#' 代表一堵墙

• '@' 是起点

• 小写字母代表钥匙

• 大写字母代表锁

我们从起点开始出发，一次移动是指向四个基本方向之一行走一个单位空间。我们不能在网格外面行走，也无法穿过一堵墙。如果途经一个钥匙，我们就把它捡起来。除非我们手里有对应的钥匙，否则无法通过锁。

假设 k 为 钥匙/锁 的个数，且满足 1 <= k <= 6，字母表中的前 k 个字母在网格中都有自己对应的一个小写和一个大写字母。换言之，每个锁有唯一对应的钥匙，每个钥匙也有唯一对应的锁。另外，代表钥匙和锁的字母互为大小写并按字母顺序排列。

返回获取所有钥匙所需要的移动的最少次数。如果无法获取所有钥匙，返回 -1 。

示例 1：

```txt

输入：grid = ["@.a.#","###.#","b.A.B"]

输出：8

解释：目标是获得所有钥匙，而不是打开所有锁。

```

示例 2：

```txt

输入：grid = ["@..aA","..B#.","....b"]

输出：6

```

示例 3:

```txt

输入: grid = ["@Aa"]

输出: -1

```

提示：

• m == grid.length

• n == grid[i].length

• 1 <= m, n <= 30

• grid[i][j] 只含有 '.', '#', '@', 'a'-``'f``' 以及 'A'-'F'

• 钥匙的数目范围是 [1, 6] 

• 每个钥匙都对应一个 不同 的字母

• 每个钥匙正好打开一个对应的锁

2867. 统计树中的合法路径数目

给你一棵 n 个节点的无向树，节点编号为 1 到 n 。给你一个整数 n 和一个长度为 n - 1 的二维整数数组 edges ，其中 edges[i] = [ui, vi] 表示节点 ui 和 vi 在树中有一条边。

请你返回树中的 合法路径数目 。

如果在节点 a 到节点 b 之间 恰好有一个 节点的编号是质数，那么我们称路径 (a, b) 是 合法的 。

注意：

• 路径 (a, b) 指的是一条从节点 a 开始到节点 b 结束的一个节点序列，序列中的节点 互不相同 ，且相邻节点之间在树上有一条边。

• 路径 (a, b) 和路径 (b, a) 视为 同一条 路径，且只计入答案 一次 。

示例 1：

```txt

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

输出：4

解释：恰好有一个质数编号的节点路径有：

• (1, 2) 因为路径 1 到 2 只包含一个质数 2 。

• (1, 3) 因为路径 1 到 3 只包含一个质数 3 。

• (1, 4) 因为路径 1 到 4 只包含一个质数 2 。

• (2, 4) 因为路径 2 到 4 只包含一个质数 2 。

只有 4 条合法路径。

```

示例 2：

```txt

输入：n = 6, edges = [[1,2],[1,3],[2,4],[3,5],[3,6]]

输出：6

解释：恰好有一个质数编号的节点路径有：

• (1, 2) 因为路径 1 到 2 只包含一个质数 2 。

• (1, 3) 因为路径 1 到 3 只包含一个质数 3 。

• (1, 4) 因为路径 1 到 4 只包含一个质数 2 。

• (1, 6) 因为路径 1 到 6 只包含一个质数 3 。

• (2, 4) 因为路径 2 到 4 只包含一个质数 2 。

• (3, 6) 因为路径 3 到 6 只包含一个质数 3 。

只有 6 条合法路径。

```

提示：

• 1 <= n <= 10^5

• edges.length == n - 1

• edges[i].length == 2

• 1 <= ui, vi <= n

• 输入保证 edges 形成一棵合法的树。

1240. 铺瓷砖

你是一位施工队的工长，根据设计师的要求准备为一套设计风格独特的房子进行室内装修。

房子的客厅大小为 n x m，为保持极简的风格，需要使用尽可能少的 正方形 瓷砖来铺盖地面。

假设正方形瓷砖的规格不限，边长都是整数。

请你帮设计师计算一下，最少需要用到多少块方形瓷砖？

示例 1：

```txt

输入：n = 2, m = 3

输出：3

解释：3 块地砖就可以铺满卧室。

 2 块 1x1 地砖 1 块 2x2 地砖

```

示例 2：

```txt

输入：n = 5, m = 8

输出：5

```

示例 3：

```txt

输入：n = 11, m = 13

输出：6

```

提示：

• 1 <= n <= 13

• 1 <= m <= 13

2851. 字符串转换

You are given two strings s and t of equal length n. You can perform the following operation on the string s:

• Remove a suffix of s of length l where 0 < l < n and append it at the start of s.

  For example, let s = 'abcd' then in one operation you can remove the suffix 'cd' and append it in front of s making s = 'cdab'.

You are also given an integer k. Return the number of ways in which s can be transformed into t in exactly k operations.

Since the answer can be large, return it modulo 10^9 + 7.

Example 1:

```txt

Input: s = "abcd", t = "cdab", k = 2

Output: 2

Explanation:

First way:

In first operation, choose suffix from index = 3, so resulting s = "dabc".

In second operation, choose suffix from index = 3, so resulting s = "cdab".

Second way:

In first operation, choose suffix from index = 1, so resulting s = "bcda".

In second operation, choose suffix from index = 1, so resulting s = "cdab".

```

Example 2:

```txt

Input: s = "ababab", t = "ababab", k = 1

Output: 2

Explanation:

First way:

Choose suffix from index = 2, so resulting s = "ababab".

Second way:

Choose suffix from index = 4, so resulting s = "ababab".

```

Constraints:

• 2 <= s.length <= 5 * 10^5

• 1 <= k <= 10^15

• s.length == t.length

• s and t consist of only lowercase English alphabets.

6456. 矩阵中严格递增的单元格数

给你一个下标从 1 开始、大小为 m x n 的整数矩阵 mat，你可以选择任一单元格作为 起始单元格 。

从起始单元格出发，你可以移动到 同一行或同一列 中的任何其他单元格，但前提是目标单元格的值 严格大于 当前单元格的值。

你可以多次重复这一过程，从一个单元格移动到另一个单元格，直到无法再进行任何移动。

请你找出从某个单元开始访问矩阵所能访问的 单元格的最大数量 。

返回一个表示可访问单元格最大数量的整数。

示例 1：

```txt

输入：mat = [[3,1],[3,4]]

输出：2

解释：上图展示了从第 1 行、第 2 列的单元格开始，可以访问 2 个单元格。可以证明，无论从哪个单元格开始，最多只能访问 2 个单元格，因此答案是 2 。

```

示例 2：

```txt

输入：mat = [[1,1],[1,1]]

输出：1

解释：由于目标单元格必须严格大于当前单元格，在本示例中只能访问 1 个单元格。

```

示例 3：

```txt

输入：mat = [[3,1,6],[-9,5,7]]

输出：4

解释：上图展示了从第 2 行、第 1 列的单元格开始，可以访问 4 个单元格。可以证明，无论从哪个单元格开始，最多只能访问 4 个单元格，因此答案是 4 。

```

提示：

• m == mat.length 

• n == mat[i].length 

• 1 <= m, n <= 10^5

• 1 <= m * n <= 10^5

• -10^5 <= mat[i][j] <= 10^5