Hard
题目描述
有一棵树（即一个连通、无向、无环图），由 n 个从 0 到 n - 1 编号的节点和恰好 n - 1 条边组成。每个节点都有一个与之相关联的值，树的根节点是节点 0。
为了表示这棵树，给你一个整数数组 nums 和一个二维数组 edges。其中 nums[i] 表示第 i 个节点的值，edges[j] = [uj, vj] 表示树中节点 uj 和 vj 之间有一条边。
如果 gcd(x, y) == 1，其中 gcd(x, y) 是 x 和 y 的最大公约数，则两个值 x 和 y 互质。
节点 i 的祖先是从节点 i 到根节点的最短路径上的任何其他节点。节点不被认为是其自身的祖先。
返回一个大小为 n 的数组 ans，其中 ans[i] 是距离节点 i 最近的祖先，使得 nums[i] 和 nums[ans[i]] 互质，如果没有这样的祖先，则为 -1。
示例 1：
输入：nums = [2,3,3,2], edges = [[0,1],[1,2],[1,3]]
输出：[-1,0,0,1]
解释：上图中，每个节点的值在括号内。
- 节点 0 没有互质祖先。
- 节点 1 只有一个祖先节点 0。它们的值互质（gcd(2,3) == 1）。
- 节点 2 有两个祖先，节点 1 和 0。节点 1 的值不互质（gcd(3,3) == 3），但节点 0 的值互质（gcd(2,3) == 1），所以节点 0 是最近的有效祖先。
- 节点 3 有两个祖先，节点 1 和 0。它与节点 1 互质（gcd(3,2) == 1），所以节点 1 是其最近的有效祖先。
示例 2：
输入：nums = [5,6,10,2,3,6,15], edges = [[0,1],[0,2],[1,3],[1,4],[2,5],[2,6]]
输出：[-1,0,-1,0,0,0,-1]
约束条件：
- nums.length == n
- 1 <= nums[i] <= 50
- 1 <= n <= 10^5
- edges.length == n - 1
- edges[j].length == 2
- 0 <= uj, vj < n
- uj != vj
解题思路
这道题需要找到每个节点的最近互质祖先。由于值的范围很小（1到50），我们可以利用这个特点来优化解法。
核心思路：
预处理互质关系：由于值只在1到50之间，我们可以预先计算出所有值对的互质关系，避免在DFS过程中重复计算gcd。
DFS遍历：从根节点开始进行深度优先搜索，对每个节点维护从根到当前路径上各个值的最近节点信息。
路径维护技巧：关键优化是维护一个数组
last[value] = node，表示当前路径上值为value的最近节点。当访问一个新节点时：- 先查找当前值的所有互质值，找到路径上最近的互质祖先
- 更新路径信息
- 递归访问子节点
- 回溯时恢复路径状态
时间复杂度优化：由于值的范围小，遍历所有可能的互质值比遍历整条路径更高效。对于每个节点，最多检查50个值，而不需要遍历可能很长的祖先链。
这种方法巧妙地利用了值域小的特点，将时间复杂度从可能的O(n×深度)优化到O(n×50)。
代码实现
class Solution {
public:
vector<int> getCoprimes(vector<int>& nums, vector<vector<int>>& edges) {
int n = nums.size();
vector<vector<int>> graph(n);
// Build adjacency list
for (auto& edge : edges) {
graph[edge[0]].push_back(edge[1]);
graph[edge[1]].push_back(edge[0]);
}
// Precompute coprime relationships
vector<vector<int>> coprimes(51);
for (int i = 1; i <= 50; i++) {
for (int j = 1; j <= 50; j++) {
if (__gcd(i, j) == 1) {
coprimes[i].push_back(j);
}
}
}
vector<int> result(n, -1);
vector<pair<int, int>> last(51, {-1, -1}); // {node, depth}
function<void(int, int, int)> dfs = [&](int node, int parent, int depth) {
int maxDepth = -1, ancestor = -1;
// Find closest coprime ancestor
for (int val : coprimes[nums[node]]) {
if (last[val].first != -1 && last[val].second > maxDepth) {
maxDepth = last[val].second;
ancestor = last[val].first;
}
}
result[node] = ancestor;
// Save current state and update
auto prev = last[nums[node]];
last[nums[node]] = {node, depth};
// Visit children
for (int child : graph[node]) {
if (child != parent) {
dfs(child, node, depth + 1);
}
}
// Restore state
last[nums[node]] = prev;
};
dfs(0, -1, 0);
return result;
}
};
class Solution:
def getCoprimes(self, nums: List[int], edges: List[List[int]]) -> List[int]:
import math
n = len(nums)
graph = [[] for _ in range(n)]
# Build adjacency list
for u, v in edges:
graph[u].append(v)
graph[v].append(u)
# Precompute coprime relationships
coprimes = [[] for _ in range(51)]
for i in range(1, 51):
for j in range(1, 51):
if math.gcd(i, j) == 1:
coprimes[i].append(j)
result = [-1] * n
last = [(-1, -1)] * 51 # (node, depth)
def dfs(node, parent, depth):
max_depth = -1
ancestor = -1
# Find closest coprime ancestor
for val in coprimes[nums[node]]:
if last[val][0] != -1 and last[val][1] > max_depth:
max_depth = last[val][1]
ancestor = last[val][0]
result[node] = ancestor
# Save current state and update
prev = last[nums[node]]
last[nums[node]] = (node, depth)
# Visit children
for child in graph[node]:
if child != parent:
dfs(child, node, depth + 1)
# Restore state
last[nums[node]] = prev
dfs(0, -1, 0)
return result
public class Solution {
public int[] GetCoprimes(int[] nums, int[][] edges) {
int n = nums.Length;
var graph = new List<int>[n];
for (int i = 0; i < n; i++) {
graph[i] = new List<int>();
}
// Build adjacency list
foreach (var edge in edges) {
graph[edge[0]].Add(edge[1]);
graph[edge[1]].Add(edge[0]);
}
// Precompute coprime relationships
var coprimes = new List<int>[51];
for (int i = 0; i <= 50; i++) {
coprimes[i] = new List<int>();
}
for (int i = 1; i <= 50; i++) {
for (int j = 1; j <= 50; j++) {
if (Gcd(i, j) == 1) {
coprimes[i].Add(j);
}
}
}
var result = new int[n];
Array.Fill(result, -1);
var last = new (int node, int depth)[51];
Array.Fill(last, (-1, -1));
void Dfs(int node, int parent, int depth) {
int maxDepth = -1, ancestor = -1;
// Find closest coprime ancestor
foreach (int val in coprimes[nums[node]]) {
if (last[val].node != -1 && last[val].depth > maxDepth) {
maxDepth = last[val].depth;
ancestor = last[val].node;
}
}
result[node] = ancestor;
// Save current state and update
var prev = last[nums[node]];
last[nums[node]] = (node, depth);
// Visit children
foreach (int child in graph[node]) {
if (child != parent) {
Dfs(child, node, depth + 1);
}
}
// Restore state
last[nums[node]] = prev;
}
Dfs(0, -1, 0);
return result;
}
private int Gcd(int a, int b) {
return b == 0 ? a : Gcd(b, a % b);
}
}
var getCoprimes = function(nums, edges) {
const n = nums.length;
const graph = Array(n).fill(null).map(() => []);
for (const [u, v] of edges) {
graph[u].push(v);
graph[v].push(u);
}
const gcd = (a, b) => b === 0 ? a : gcd(b, a % b);
const result = Array(n).fill(-1);
const ancestors = Array(51).fill(null).map(() => []);
const dfs = (node, parent) => {
let maxDepth = -1;
let closestAncestor = -1;
for (let val = 1; val <= 50; val++) {
if (ancestors[val].length > 0 && gcd(nums[node], val) === 1) {
const [ancestorNode, depth] = ancestors[val][ancestors[val].length - 1];
if (depth > maxDepth) {
maxDepth = depth;
closestAncestor = ancestorNode;
}
}
}
result[node] = closestAncestor;
ancestors[nums[node]].push([node, ancestors[nums[node]].length]);
for (const child of graph[node]) {
if (child !== parent) {
dfs(child, node);
}
}
ancestors[nums[node]].pop();
};
dfs(0, -1);
return result;
};
复杂度分析
| 复杂度类型 | 分析 |
|---|---|
| 时间复杂度 | O(n × 50 + 50²) = O(n)，其中 n 为节点数。预处理互质关系需要 O(50²)，DFS 遍历每个节点时最多检查50个值 |
| 空间复杂度 | O(n + 50²) = O(n)，用于存储图的邻接表、互质关系表和递归栈空间 |