Solution for a more general problem (answering queries online)
Intuition\n Describe your first thoughts on how to solve this problem. \nMST + biary lifting \n# Approach\n Describe your approach to solving the problem. \nBui
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nMST + biary lifting \n# Approach\n<!-- Describe your approach to solving the problem. -->\nBuild MST, adding dummy edges with INF weight if initial graph is disconnected. Binary lifting to precompute max weight edges for every node to every other node at dost 2^i.\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nMST Kruskal in O(NlogN) + precompute binary lifting in O(NlogN);\nquery in O(logN)\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\n#include <bits/stdc++.h>\n\n#include <algorithm>\n#include <cassert>\n#include <vector>\n\nnamespace atcoder {\n\nstruct dsu {\n  public:\n    dsu() : _n(0) {}\n    explicit dsu(int n) : _n(n), parent_or_size(n, -1) {}\n\n    int merge(int a, int b) {\n        assert(0 <= a && a < _n);\n        assert(0 <= b && b < _n);\n        int x = leader(a), y = leader(b);\n        if (x == y) return x;\n        if (-parent_or_size[x] < -parent_or_size[y]) std::swap(x, y);\n        parent_or_size[x] += parent_or_size[y];\n        parent_or_size[y] = x;\n        return x;\n    }\n\n    bool same(int a, int b) {\n        assert(0 <= a && a < _n);\n        assert(0 <= b && b < _n);\n        return leader(a) == leader(b);\n    }\n\n    int leader(int a) {\n        assert(0 <= a && a < _n);\n        if (parent_or_size[a] < 0) return a;\n        return parent_or_size[a] = leader(parent_or_size[a]);\n    }\n\n    int size(int a) {\n        assert(0 <= a && a < _n);\n        return -parent_or_size[leader(a)];\n    }\n\n    std::vector<std::vector<int>> groups() {\n        std::vector<int> leader_buf(_n), group_size(_n);\n        for (int i = 0; i < _n; i++) {\n            leader_buf[i] = leader(i);\n            group_size[leader_buf[i]]++;\n        }\n        std::vector<std::vector<int>> result(_n);\n        for (int i = 0; i < _n; i++) {\n            result[i].reserve(group_size[i]);\n        }\n        for (int i = 0; i < _n; i++) {\n            result[leader_buf[i]].push_back(i);\n        }\n        result.erase(\n            std::remove_if(result.begin(), result.end(),\n                           [&](const std::vector<int>& v) { return v.empty(); }),\n            result.end());\n        return result;\n    }\n\n  private:\n    int _n;\n    std::vector<int> parent_or_size;\n};\n\n}  // namespace atcoder\n\n\nusing namespace std;\nusing namespace atcoder;\n\n\n// https://www.geeksforgeeks.org/maximum-weighted-edge-in-path-between-two-nodes-in-an-n-ary-tree-using-binary-lifting/\nconst int N = 100005;\n \n// Depths of Nodes\nvector<int> level(N);\nconst int LG = 20;\n \n// Parent at every 2^i level\nvector<vector<int> > dp(LG, vector<int>(N));\n \n// Maximum node at every 2^i level\nvector<vector<int> > mx(LG, vector<int>(N));\n \n \n// Function to traverse the nodes\n// using the Depth-First Search Traversal\nvoid dfs_lca(int a, int par, int lev, int n, vector<vector<pair<int, int>>> &g)\n{\n\n    dp[0][a] = par;\n    level[a] = lev;\n    \n    for (auto i : g[a]) {\n \n        // Condition to check if its\n        // equal to its parent then skip\n        if (i.first == par)\n            continue;\n        mx[0][i.first] = i.second;\n \n        // DFS Recursive Call\n        dfs_lca(i.first, a, lev + 1, n, g);\n    }\n}\n \n// Function to find the ancestor\nvoid find_ancestor(int n)\n{\n \n    // Loop to set every 2^i distance\n    for (int i = 1; i < LG; i++) {\n        // Loop to calculate for\n        // each node in the N-ary tree\n        for (int j = 1; j <= n; j++) {\n            dp[i][j]\n                = dp[i - 1][dp[i - 1][j]];\n \n            // Storing maximum edge\n            mx[i][j]\n                = max(mx[i - 1][j],\n                      mx[i - 1][dp[i - 1][j]]);\n        }\n    }\n}\n \nint getMax(int a, int b)\n{\n    // Swapping if node a is at more depth\n    // than node b because we will\n    // always take at more depth\n    if (level[b] < level[a])\n        swap(a, b);\n \n    int ans = 0;\n \n    // Difference between the depth of\n    // the two given nodes\n    int diff = level[b] - level[a];\n    while (diff > 0) {\n        int log = log2(diff);\n        ans = max(ans, mx[log][b]);\n \n        // Changing Node B to its\n        // parent at 2 ^ i distance\n        b = dp[log][b];\n \n        // Subtracting distance by 2^i\n        diff -= (1 << log);\n    }\n \n    // Take both a, b to its\n    // lca and find maximum\n    while (a != b) {\n        int i = level[a] == 0 ? 0 : log2(level[a]);\n \n        // Loop to find the 2^ith\n        // parent that is different\n        // for both a and b i.e below the lca \n        while (i > 0\n               && dp[i][a] == dp[i][b])\n            i--;\n \n        // Updating ans\n        ans = max(ans, mx[i][a]);\n        ans = max(ans, mx[i][b]);\n \n        // Changing value to its parent\n        a = dp[i][a];\n        b = dp[i][b];\n    }\n    return ans;\n}\n \n// Function to compute the Least\n// common Ancestor\nvoid compute_lca(int n, vector<vector<pair<int, int>>> &g)\n{\n    dfs_lca(1, 0, 1, n, g);\n    find_ancestor(n);\n}\n\n\nclass Solution {\npublic:\n    vector<vector<pair<int, int>>> mst(int n, vector<vector<int>>& edgeList, dsu& dsu){\n        sort(edgeList.begin(), edgeList.end(), [&](const vector<int> &le, const vector<int> &ri){\n            return le[2] < ri[2];\n        });\n        \n\n        vector<vector<pair<int, int>>> g(n + 1);\n        int cnt = 0;\n        for(auto &edge : edgeList){\n            int u = edge[0] + 1;\n            int v = edge[1] + 1;\n            int dist = edge[2];\n            if(!dsu.same(u, v)){\n                g[u].push_back({v, dist});\n                g[v].push_back({u, dist});\n                dsu.merge(u, v);\n                ++cnt;\n            }\n        }\n\n        auto gr = dsu.groups();\n        for(int i = 2; i < (int) gr.size(); ++i){\n            if(!gr[0].empty() && !gr[i].empty()){\n                g[gr[1][0]].push_back({gr[i][0], 2e9});\n                g[gr[i][0]].push_back({gr[1][0], 2e9});\n            }\n        }\n        return g;\n    }\n\n    vector<bool> distanceLimitedPathsExist(int n, vector<vector<int>>& edgeList, vector<vector<int>>& queries) {\n        dsu dsu(n + 1);\n        vector<vector<pair<int, int>>> g = mst(n, edgeList, dsu);\n        compute_lca(n, g);\n        vector<bool> ans;\n        for(auto &q : queries){\n            int u = q[0] + 1;\n            int v = q[1] + 1;\n            int limit = q[2];\n            bool res = getMax(u, v) < limit;\n            ans.push_back(res);\n        }\n        return ans;\n    }\n};\n```
['C++']