题解

问题解释

把所有边权不超过 $W$ 的边保留下来．点 $x$ 的答案，就是使得 $x$ 第一次属于某个简单环的最小 $W$．

正解先用 Kruskal 求一棵最小生成树．每条非树边与树上两端之间的路径组成一个环，于是问题转化为若干次树上路径赋值：按照非树边权从小到大处理，把一条路径上还没有答案的点赋为当前边权．

算法 0：枚举权值并求桥

无向图中的一条边属于某个简单环，当且仅当它不是桥．因此，一个点属于某个简单环，当且仅当它与至少一条非桥边相连．

枚举不同边权 $W$，每次建出所有边权不超过 $W$ 的子图，用 Tarjan 算法求桥，并为第一次与非桥边相连的点记录答案．设不同边权数量为 $K$，时间复杂度为 $O(K(n+m))$，空间复杂度为 $O(n+m)$．

预期通过 subtask 1、2、4，共 $45$ 分．

算法 1：逐点遍历树上路径

先求最小生成树，并预处理父亲和深度．对于每条非树边 $(u,v,w)$，比较两端深度，每次将较深端向父亲移动一步，并用 $w$ 更新经过的点，直到两端相遇；相遇点也在这条路径上，需要更新一次．

设非树边数量为 $q=m-n+1$，一条路径最多经过 $n$ 个点，因此时间复杂度为 $O(m\log m+qn)$，空间复杂度为 $O(n+m)$．

预期通过 subtask 1、3、4，共 $45$ 分．

算法 2：LCA 与并查集跳点

转化为最小生成树上的路径

用 Kruskal 求一棵最小生成树 $T$．对于一条未加入 $T$ 的边 $e=(u,v,w)$，它与 $T$ 上 $u$ 到 $v$ 的唯一路径组成一个基本环．

Kruskal 拒绝 $e$ 时，$u,v$ 已经被此前选中的树边连通，因此树上路径的每条边权都不超过 $w$．基本环又包含权值为 $w$ 的边 $e$，所以这个环的瓶颈值恰好为 $w$．

只考虑这些基本环不会漏掉最优答案．设一个瓶颈值为 $W$ 的简单环经过点 $x$：

• 如果环上与 $x$ 相邻的某条边是非树边，取这条边，它在最小生成树上的端点路径包含 $x$；
• 否则，与 $x$ 相邻的两条环边都是树边．任选其中一条树边 $f$，删除 $f$ 后，原环上除 $f$ 外的路径仍然跨过这个割，因此这段路径中存在一条非树边 $e$．边 $e$ 的树上端点路径经过 $f$，从而也经过 $x$．

这条非树边位于原环上，所以 $w_e\le W$．因此，每个合法环都能找到一个瓶颈值不更大的基本环覆盖同一个点．

于是，每条非树边 $(u,v,w)$ 对应一次操作：用 $w$ 更新最小生成树上 $u$ 到 $v$ 路径的所有点．

求 LCA 后直接跳过已赋值点

把最小生成树根定，并用倍增预处理 LCA．再维护一个跳跃并查集：

• find(x) 表示从 $x$ 开始向父亲走，第一个还没有获得答案的点；
• 点 $x$ 获得答案后，令它直接合并到 find(parent[x])，以后访问到 $x$ 时便会跳过它；
• 编号 $0$ 作为根的父亲和哨兵，不对应实际点．

非树边已经按边权从小到大排列．处理 $(u,v,w)$ 时，先求出

$$l=\operatorname{LCA}(u,v).$$

对于 $u$ 和 $v$ 两侧分别执行以下过程：

1. 令 $x=\operatorname{find}(u)$；
2. 当 $\operatorname{depth}(x)>\operatorname{depth}(l)$ 时，令 $ans_x=w$，把 $x$ 合并到 find(parent[x])，再重新令 $x=\operatorname{find}(x)$；
3. 另一侧同理．

上述过程处理了路径中除 $l$ 外的所有尚未赋值点．最后，如果 find(l)==l，说明 $l$ 还没有答案，就令 $ans_l=w$ 并把它也合并到父亲．如果 find(l)!=l，说明 $l$ 以前已经被更小或相等的权值处理过，不能把跳跃后到达的祖先误认为本次路径上的点．

每个点第一次被某条路径覆盖时得到答案，随后立即被并查集跳过，所以每个点至多真正处理一次．

预期通过所有 subtask．

正确性证明

引理 1

任意非树边 $(u,v,w)$ 与最小生成树上 $u$ 到 $v$ 的路径构成的基本环，瓶颈值为 $w$．

证明． Kruskal 处理该边时，$u,v$ 已经被权值不超过 $w$ 的树边连通；基本环又包含权值为 $w$ 的该非树边，因此环上最大边权恰为 $w$．证毕．

引理 2

若点 $x$ 属于瓶颈值为 $W$ 的简单环，则存在一条权值不超过 $W$ 的非树边，其在最小生成树上的端点路径经过 $x$．

证明． 若环上与 $x$ 相邻的边存在非树边，直接取它．否则，任选一条与 $x$ 相邻的树边 $f$．删除 $f$ 形成的割还会被环上另一条边 $e$ 跨过；树中只有 $f$ 跨过这个割，所以 $e$ 是非树边．它的树上端点路径经过 $f$，从而经过 $x$，且 $w_e\le W$．证毕．

引理 3

处理非树边 $(u,v,w)$ 时，算法恰好给路径 $u\leadsto v$ 上所有尚未赋值的点赋值．

证明． 令 $l=\operatorname{LCA}(u,v)$．路径由 $u\leadsto l$ 和 $v\leadsto l$ 两条祖先链组成．find 只会沿父亲方向越过已经赋值的点，所以当返回点的深度大于 $l$ 时，该点一定是对应祖先链上尚未赋值的点；将它赋值并合并到父亲后，继续处理链上的下一个未赋值点．深度不再大于 $l$ 时，该侧除 $l$ 外已无未赋值点．最后仅在 $l$ 本身尚未赋值时处理它，因此不会越过 $l$ 误处理路径外的祖先．证毕．

引理 4

每个得到答案的点记录的权值，是覆盖它的所有基本环瓶颈值中的最小值．

证明． 非树边按权值非降序处理．根据引理 3，一个点第一次被覆盖时写入当前权值，随后被并查集永久跳过，不会被更大的权值改写，因此记录的就是最小值．证毕．

定理

算法输出的每个点答案均正确．

证明． 根据引理 1，每次路径赋值都来自一个合法基本环．根据引理 2，任何经过某点的简单环，都能找到一个瓶颈值不更大的基本环覆盖该点．再由引理 4，算法记录的正是所有包含该点的简单环瓶颈值中的最小值．没有被任何路径覆盖的点不属于任何简单环，输出 $-1$ 正确．证毕．

复杂度分析

Kruskal 排序的时间复杂度为 $O(m\log m)$．倍增预处理和全部 LCA 查询的时间复杂度为 $O((n+m)\log n)$．跳跃并查集中每个点只会被删除一次，全部操作的摊还时间复杂度为 $O((n+m)\alpha(n))$．

总时间复杂度为

$$O(m\log m+(n+m)\log n),$$

空间复杂度为 $O(n\log n+m)$．

实现细节

• 最小生成树可能是一条长链，使用迭代遍历求深度和第一层父亲，避免 DFS 爆栈．
• 跳跃并查集的 find 使用迭代路径压缩，避免尚未压缩的长链造成递归过深．
• 根被赋值后合并到哨兵 $0$；判断 LCA 是否尚未赋值时必须使用 find(l)==l．
• 相同权值的非树边以任意顺序处理都不影响答案．

参考代码

#include <algorithm>
#include <iostream>
#include <numeric>
#include <utility>
#include <vector>

struct Edge {
    int u;
    int v;
    int weight;
};

class DisjointSet {
public:
    explicit DisjointSet(int n) : parent_(n + 1), size_(n + 1, 1) {
        std::iota(parent_.begin(), parent_.end(), 0);
    }

    int find(int vertex) {
        return parent_[vertex] == vertex
            ? vertex
            : parent_[vertex] = find(parent_[vertex]);
    }

    bool unite(int left, int right) {
        left = find(left);
        right = find(right);
        if (left == right) return false;
        if (size_[left] < size_[right]) std::swap(left, right);
        parent_[right] = left;
        size_[left] += size_[right];
        return true;
    }

private:
    std::vector<int> parent_;
    std::vector<int> size_;
};

class JumpSet {
public:
    explicit JumpSet(int n) : next_(n + 1) {
        std::iota(next_.begin(), next_.end(), 0);
    }

    int find(int vertex) {
        int root = vertex;
        while (next_[root] != root) root = next_[root];
        while (next_[vertex] != vertex) {
            int following = next_[vertex];
            next_[vertex] = root;
            vertex = following;
        }
        return root;
    }

    void erase_to(int vertex, int parent) {
        next_[vertex] = find(parent);
    }

private:
    std::vector<int> next_;
};

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, m;
    std::cin >> n >> m;
    std::vector<Edge> edges(m);
    for (Edge& edge : edges) {
        std::cin >> edge.u >> edge.v >> edge.weight;
    }
    std::sort(edges.begin(), edges.end(), [](const Edge& left, const Edge& right) {
        if (left.weight != right.weight) return left.weight < right.weight;
        if (left.u != right.u) return left.u < right.u;
        return left.v < right.v;
    });

    DisjointSet kruskal(n);
    std::vector<std::vector<int>> tree(n + 1);
    std::vector<Edge> non_tree_edges;
    non_tree_edges.reserve(m - n + 1);
    for (const Edge& edge : edges) {
        if (kruskal.unite(edge.u, edge.v)) {
            tree[edge.u].push_back(edge.v);
            tree[edge.v].push_back(edge.u);
        } else {
            non_tree_edges.push_back(edge);
        }
    }

    int levels = 1;
    while ((1 << levels) <= n) ++levels;
    std::vector<std::vector<int>> up(levels, std::vector<int>(n + 1, 0));
    std::vector<int> depth(n + 1, 0);
    std::vector<int> order(1, 1);
    order.reserve(n);
    for (std::size_t index = 0; index < order.size(); ++index) {
        int vertex = order[index];
        for (int neighbor : tree[vertex]) {
            if (neighbor == up[0][vertex]) continue;
            up[0][neighbor] = vertex;
            depth[neighbor] = depth[vertex] + 1;
            order.push_back(neighbor);
        }
    }
    for (int level = 1; level < levels; ++level) {
        for (int vertex = 1; vertex <= n; ++vertex) {
            up[level][vertex] = up[level - 1][up[level - 1][vertex]];
        }
    }

    auto lca = [&](int left, int right) {
        if (depth[left] < depth[right]) std::swap(left, right);
        int difference = depth[left] - depth[right];
        for (int level = 0; level < levels; ++level) {
            if ((difference >> level) & 1) left = up[level][left];
        }
        if (left == right) return left;
        for (int level = levels - 1; level >= 0; --level) {
            if (up[level][left] != up[level][right]) {
                left = up[level][left];
                right = up[level][right];
            }
        }
        return up[0][left];
    };

    std::vector<int> answer(n + 1, -1);
    JumpSet unassigned(n);

    auto paint_up = [&](int vertex, int ancestor, int weight) {
        int current = unassigned.find(vertex);
        while (depth[current] > depth[ancestor]) {
            answer[current] = weight;
            unassigned.erase_to(current, up[0][current]);
            current = unassigned.find(current);
        }
    };

    for (const Edge& edge : non_tree_edges) {
        int ancestor = lca(edge.u, edge.v);
        paint_up(edge.u, ancestor, edge.weight);
        paint_up(edge.v, ancestor, edge.weight);
        if (unassigned.find(ancestor) == ancestor) {
            answer[ancestor] = edge.weight;
            unassigned.erase_to(ancestor, up[0][ancestor]);
        }
    }

    for (int vertex = 1; vertex <= n; ++vertex) {
        if (vertex > 1) std::cout << ' ';
        std::cout << answer[vertex];
    }
    std::cout << '\n';
    return 0;
}