1766. Tree of Coprimes
Approach
DFS tree with per-value stacks of (node, depth); for each node check coprime values for deepest ancestor.
Key Techniques
Array problems involve manipulating elements stored in a contiguous block of memory. Key techniques include two-pointer traversal, prefix sums, sliding windows, and in-place partitioning. In C#, arrays are zero-indexed and fixed in size — use List<T> when you need dynamic resizing.
Math problems test number theory, combinatorics, and modular arithmetic. Common tools: GCD/LCM (Euclidean algorithm), prime sieve, modular inverse (Fermat's little theorem), digit manipulation, and bit tricks. Overflow is a key concern in C# — use long when products may exceed 2³¹.
DFS explores as far as possible before backtracking. Use it for path finding, cycle detection, connected components, and tree traversal. Implement recursively (implicit call stack) or iteratively with an explicit Stack<T>. Mark visited nodes to avoid infinite loops in graphs.
// Approach: DFS tree with per-value stacks of (node, depth); for each node check coprime values for deepest ancestor.
// Time: O(n * 50²) Space: O(n)
public class Solution
{
public int[] GetCoprimes(int[] nums, int[][] edges)
{
int[] ans = new int[nums.Length];
Array.Fill(ans, -1);
List<int>[] tree = new List<int>[nums.Length];
// stacks[i] := (node, depth)s of nodes with value i
Stack<(int, int)>[] stacks = new Stack<(int, int)>[kMax + 1];
for (int i = 0; i < nums.Length; ++i)
tree[i] = new List<int>();
for (int i = 1; i <= kMax; ++i)
stacks[i] = new Stack<(int, int)>();
foreach (int[] edge in edges)
{
int u = edge[0];
int v = edge[1];
tree[u].Add(v);
tree[v].Add(u);
}
Dfs(tree, 0, -1, 0, nums, stacks, ans);
return ans;
}
private const int kMax = 50;
private void Dfs(List<int>[] tree, int u, int prev, int depth, int[] nums,
Stack<(int, int)>[] stacks, int[] ans)
{
ans[u] = GetAncestor(u, stacks, nums);
stacks[nums[u]].Push((u, depth));
foreach (int v in tree[u])
{
if (v != prev)
Dfs(tree, v, u, depth + 1, nums, stacks, ans);
}
stacks[nums[u]].Pop();
}
private int GetAncestor(int u, Stack<(int, int)>[] stacks, int[] nums)
{
int maxNode = -1;
int maxDepth = -1;
for (int i = 1; i <= kMax; ++i)
{
if (stacks[i].Count > 0 && stacks[i].Peek().Item2 > maxDepth && Gcd(nums[u], i) == 1)
{
maxNode = stacks[i].Peek().Item1;
maxDepth = stacks[i].Peek().Item2;
}
}
return maxNode;
}
private int Gcd(int a, int b)
{
return b == 0 ? a : Gcd(b, a % b);
}
}