Tap here to switch tabs
Problem
Submissions

Problem: Tree of Coprimes

Try to solve the Tree of Coprimes problem.

Statement

You are given a tree with nn nodes numbered from 00 to n−1n - 1 rooted at node 00, represented by an integer array nums of length nn and a 22D integer array edges of length n−1n - 1, where edges[j] = [u_j, v_j] indicates an undirected edge between nodes u_j and v_j. Each node i has a value nums[i].

Two integers are coprime if their greatest common divisor is 11.

For each node i from 00 to n−1n - 1, find the closest ancestor node whose value is coprime to nums[i].

Return an array ans of length nn where ans[i] is the closest coprime ancestor of node i, or −1-1 if no such ancestor exists.

Note: A node u is an ancestor of node v if u lies on the path from the root node 00 to node v, and u is not equal to v.

Constraints:

  • nums.length ==n== n

  • 1≤1 \leq nums[i] ≤50\leq 50

  • 1≤n≤1051 \leq n \leq 10^5

  • edges.length ==n−1== n - 1

  • edges[j].length ==2== 2

  • 0≤0 \leq u_j, v_j <n< n

  • u_j ≠\neq v_j

⋮
Tap here to switch tabs
Problem
Submissions

Problem: Tree of Coprimes

Try to solve the Tree of Coprimes problem.

Statement

You are given a tree with nn nodes numbered from 00 to n−1n - 1 rooted at node 00, represented by an integer array nums of length nn and a 22D integer array edges of length n−1n - 1, where edges[j] = [u_j, v_j] indicates an undirected edge between nodes u_j and v_j. Each node i has a value nums[i].

Two integers are coprime if their greatest common divisor is 11.

For each node i from 00 to n−1n - 1, find the closest ancestor node whose value is coprime to nums[i].

Return an array ans of length nn where ans[i] is the closest coprime ancestor of node i, or −1-1 if no such ancestor exists.

Note: A node u is an ancestor of node v if u lies on the path from the root node 00 to node v, and u is not equal to v.

Constraints:

  • nums.length ==n== n

  • 1≤1 \leq nums[i] ≤50\leq 50

  • 1≤n≤1051 \leq n \leq 10^5

  • edges.length ==n−1== n - 1

  • edges[j].length ==2== 2

  • 0≤0 \leq u_j, v_j <n< n

  • u_j ≠\neq v_j