# LeetCode 1766. Tree of Coprimes

```struct Node
{
int value;
int next;
}edge[500005];

int pos;
void init()
{
pos=0;
}

{
edge[pos].value = y;
}

int gcd(int x, int y)
{
if(x<y)
swap(x,y);

return x%y==0 ? y : gcd(x%y, y);
}

class Solution {
public:
vector<int> p[55];
int s[100005];
int s_p;
vector<int> a[55];
int vis[100005];
vector<int> ans;
vector<int> getCoprimes(vector<int>& nums, vector<vector<int>>& edges) {

init();
for(int i=0;i<edges.size();i++)
{
}

for(int i=1;i<=50;i++)
{
for(int j=1;j<=50;j++)
{
if(gcd(i,j)==1)
{
p[i].push_back(j);
}
}
}

memset(vis,0,sizeof(vis));
s_p=0;

for(int i=0;i<nums.size();i++)
{
ans.push_back(0);
}
s[s_p] = 0;
a[nums[0]].push_back(0);
vis[0]=1;
ans[0]=-1;
dfs(0, nums);

return ans;

}

void dfs(int root, vector<int>& nums)
{

{
int v = edge[i].value;
if(vis[v]==1)
continue;

int res = -1;
for(int j=0;j<p[nums[v]].size();j++)
{
if(a[p[nums[v]][j]].size()>0)
{
res = max(res, a[p[nums[v]][j]][a[p[nums[v]][j]].size()-1]);
}
}

if(res!=-1)
ans[v] = s[res];
else
ans[v] = -1;

vis[v]=1;

s[++s_p] = v;
a[nums[v]].push_back(s_p);

dfs(v, nums);

s_p--;
a[nums[v]].pop_back();
}
}
};```

0 条评论

• ### LeetCode 543. Diameter of Binary Tree

Given a binary tree, you need to compute the length of the diameter of the tree....

• ### LeetCode: Maximum Depth of Binary Tree

Given a binary tree, find its maximum depth.

• ### 【leetcode】Minimum Depth of Binary Tree

Given a binary tree, find its minimum depth.

• ### 【leetcode】Maximum Depth of Binary Tree

Given a binary tree, find its maximum depth.

• ### Leetcode: Minimum Depth of Binary Tree

题目： Given a binary tree, find its minimum depth.

• ### LeetCode 1516. Move Sub-Tree of N-Ary Tree（DFS）

Given the root of an N-ary tree of unique values, and two nodes of the tree p an...

• ### Leetcode 111 Minimum Depth of Binary Tree

Given a binary tree, find its minimum depth. The minimum depth is the number o...

• ### Leetcode 104 Maximum Depth of Binary Tree

Given a binary tree, find its maximum depth. The maximum depth is the number o...

• ### LeetCode 662. Maximum Width of Binary Tree

Given a binary tree, write a function to get the maximum width of the given tree...

• ### Leetcode-Easy 543. Diameter of Binary Tree

543. Diameter of Binary Tree 描述： 求二叉树最长路径长度 ? 思路： 深度优先搜索 代码 # Definit...

• ### Leetcode-Easy 572. Subtree of Another Tree

572. Subtree of Another Tree 描述： 给定两个二叉树s和t，判断t是否s的一个子树。要求结构完全一致 ? ? 思...

• ### Leetcode 104. Maximum Depth of Binary Tree

版权声明：博客文章都是作者辛苦整理的，转载请注明出处，谢谢！ https://blog.csdn....

• ### Leetcode 111. Minimum Depth of Binary Tree

版权声明：博客文章都是作者辛苦整理的，转载请注明出处，谢谢！ https://blog.csdn....

• ### 【LeetCode】104. Maximum Depth of Binary Tree

版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。 ...

• ### LeetCode 104 Maximum Depth of Binary Tree

给予一颗二叉树，返回其树的深度。 最大深度是从根节点到最远叶节点的最长路径上的节点数。

• ### LeetCode 0104 - Maximum Depth of Binary Tree

Given a binary tree, find its maximum depth.