稀碎从零算法笔记Day46-LeetCode:互质树

这几天有点懈怠了

题型：树、DFS、BSF、数学

链接：1766. 互质树 - 力扣（LeetCode）

来源：LeetCode

题目描述

给你一个 n 个节点的树（也就是一个无环连通无向图），节点编号从 0 到 n - 1 ，且恰好有 n - 1 条边，每个节点有一个值。树的 根节点 为 0 号点。

给你一个整数数组 nums 和一个二维数组 edges 来表示这棵树。nums[i] 表示第 i 个点的值，edges[j] = [uj, vj] 表示节点 uj 和节点 vj 在树中有一条边。

当 gcd(x, y) == 1 ，我们称两个数 x 和 y 是 互质的 ，其中 gcd(x, y) 是 x 和 y 的 最大公约数 。

从节点 i 到 根 最短路径上的点都是节点 i 的祖先节点。一个节点 不是 它自己的祖先节点。

请你返回一个大小为 n 的数组 ans ，其中 ans[i]是离节点 i 最近的祖先节点且满足 nums[i] 和 nums[ans[i]] 是 互质的 ，如果不存在这样的祖先节点，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 <= 105
• edges.length == n - 1
• edges[j].length == 2
• 0 <= uj, vj < n
• uj != vj

题目思路（纯看的灵茶山艾府的题解，无思路）

题目都没看懂....

C++代码

    vector<int>coprime[51];//50哥节点极限是，那就将1-50的情况都表示出来
    
    //初始化coprime数组
    auto init = []
    {
        for(int i = 1;i<51;i++)
            for(int j = 1;j<51;j++)
            {
                if(gcd(i,j) == 1)//如果最大公因数为1 其中j是i的父亲
                {
                    coprime[i].push_back(j);
                }
            }
        return 0;
    }();

class Solution {
public:
    vector<vector<int>> g;
    vector<int>answer;//答案
    pair<int,int>depth_pair[51] ;//深度 编号

    //dfs
    void dfs(int x,int fa,int depth,vector<int> &nums)
    {
        int val = nums[x];
        int max_depth = 0;
        for(int temp : coprime[val])
        {
            auto [depth,id] = depth_pair[temp];
            if(depth > max_depth)
            {
                max_depth = depth;
                answer[x] = id;

            }
        }
        auto tmp = depth_pair[val]; 
        depth_pair[val] = {depth,x};
        for(int y : g[x])
            if(y != fa)
                dfs(y,x,depth+ 1 ,nums);//递归
        depth_pair[val] = tmp;
    }

    vector<int> getCoprimes(vector<int>& nums, vector<vector<int>>& edges) {
        int n = nums.size();
        g.resize(n);
        for(auto &e : edges)
        {
            int x = e[0], y = e[1];
            g[x].push_back(y);
            g[y].push_back(x);
        }
        answer.resize(n ,-1);
        dfs(0,-1,1,nums);
        return answer;
        
    }
};

结算页面