Problem Link

题目大意

给定 $n$ 个点 $m$ 条边的带权无向图，对每个 $k$ 求出一条 $1\to k$ 的无重边路径，最小化路径上最大边权与最小边权的和。

数据范围：$n,m\le 3\times 10^5$。

思路分析

考虑暴力，枚举最大边权，然后求出 $1$ 到每个点的最小边，容易发现一条边 $e$ 能被某个 $1\to u$ 的无重边路径经过当且仅当 $e$ 所属边双联通分量在 $1,u$ 所属边双联通分量的路径上。

那么我们按顺序从小到大枚举边，并将边双联通分量缩点。

• 如果一条边连接两个联通块，那么这条边一定在原图的最小生成树上，我们可以先求出这些边，在树上维护问题。
• 如果一条边连接两个不同的边双联通分量 $u,v$，那么就是把他们之间的路径全部缩成一个点，把 $\mathrm{LCA}(u,v)$ 内的每个点的最小边用 $u,v$ 的最小边和边权的最小值更新，并把这个值加当前边权更新子树内每个点的答案。
• 如果一条边连接两个相同的边双联通分量，由于我们从小到大加入边，那么这条边显然不可能更新任何答案。

注意到每个边双联通分量都是最小生成树上的连通块，我们可以直接在最小生成树用并查集上维护这个过程，那么第二类边就是对子树权值 chkmin。

但是注意加入这类边前可能有第二类边在这个点的祖先上对答案做 chkmin 操作，但是操作时的最大边权并不对，我们只要在每个点第一次和根节点联通时把之前对答案的 chkmin 操作全部删掉即可。

我们需要一棵线段树维护区间 chkmin，单点修改和单点查询。

时间复杂度 $\mathcal O((n+m)\log n)$。

代码呈现

#include<bits/stdc++.h>
using namespace std;
const int MAXN=3e5+5,inf=2e9;
inline void chkmin(int &x,const int &y) { x=x<y?x:y; }
int n,m;
struct Segt {
	int tr[MAXN<<2];
	void psd(int u) { chkmin(tr[u<<1],tr[u]),chkmin(tr[u<<1|1],tr[u]),tr[u]=inf; }
	void init() { fill(tr,tr+(MAXN<<2),inf); }
	void set(int u,int x,int l=1,int r=n,int p=1) {
		if(l==r) return tr[p]=x,void();
		int mid=(l+r)>>1; psd(p);
		u<=mid?set(u,x,l,mid,p<<1):set(u,x,mid+1,r,p<<1|1);
	}
	void upd(int ul,int ur,int x,int l=1,int r=n,int p=1) {
		if(ul<=l&&r<=ur) return chkmin(tr[p],x);
		int mid=(l+r)>>1; psd(p);
		if(ul<=mid) upd(ul,ur,x,l,mid,p<<1);
		if(mid<ur) upd(ul,ur,x,mid+1,r,p<<1|1);
	}
	int qry(int u,int l=1,int r=n,int p=1) {
		if(l==r) return tr[p];
		int mid=(l+r)>>1; psd(p);
		return u<=mid?qry(u,l,mid,p<<1):qry(u,mid+1,r,p<<1|1);
	}
}	Tv,Tw;
struct DSU {
	int dsu[MAXN];
	void init() { iota(dsu+1,dsu+n+1,1); }
	int find(int x) { return dsu[x]^x?dsu[x]=find(dsu[x]):x; }
	bool merge(int x,int y) {
		x=find(x),y=find(y);
		if(x==y) return false;
		return dsu[x]=y,true;
	}
}	S,B;
struct Edge { int u,v,w; };
vector <int> G[MAXN];
int dep[MAXN],L[MAXN],R[MAXN],dcnt,fa[MAXN];
void dfs(int u,int fz) {
	vector <int> s;
	L[u]=++dcnt,fa[u]=fz,dep[u]=dep[fz]+1;
	for(int v:G[u]) if(v^fz) dfs(v,u),s.push_back(v);
	R[u]=dcnt,G[u].swap(s);
}
void ins(int u,int w) {
	if(S.find(u)!=1) return ;
	Tw.set(L[u],Tv.qry(L[u])+w);
	for(int v:G[u]) ins(v,w);
}
signed main() {
	scanf("%d%d",&n,&m);
	vector <Edge> E(m);
	for(auto &e:E) scanf("%d%d%d",&e.u,&e.v,&e.w);
	sort(E.begin(),E.end(),[&](auto i,auto j){ return i.w<j.w; });
	S.init();
	for(auto e:E) if(S.merge(e.u,e.v)) G[e.u].push_back(e.v),G[e.v].push_back(e.u);
	dfs(1,0),S.init(),B.init(),Tv.init(),Tw.init();
	for(auto e:E) {
		int u=e.u,v=e.v,w=e.w;
		if(S.find(u)!=S.find(v)) {
			if(fa[u]==v) swap(u,v);
			Tv.upd(L[v],R[v],w),S.dsu[v]=u,ins(v,w);
		} else {
			u=B.find(u),v=B.find(v),w=min({w,Tv.qry(L[u]),Tv.qry(L[v])});
			while(u^v) {
				if(dep[u]<dep[v]) swap(u,v);
				B.dsu[u]=fa[u],u=B.find(u);
			}
			Tv.upd(L[u],R[u],w),Tw.upd(L[u],R[u],w+e.w);
		}
	}
	for(int i=2;i<=n;++i) printf("%d\n",Tw.qry(L[i]));
	return 0;
}

#include <bits/stdc++.h>
 
using namespace std;
 
const int M = 3e5 + 10;
const int T = (1 << 20) + 239;
const int BIG = 2e9 + 239;
 
int mn[T], add[T];
 
void build(int i, int l, int r) {
    mn[i] = BIG;
    add[i] = BIG;
    if (r - l == 1) {
        return;
    }
    int mid = (l + r) / 2;
    build(2 * i + 1, l, mid);
    build(2 * i + 2, mid, r);
}
 
int getmin(int i, int l, int r, int ql, int qr) {
    if (qr <= l || r <= ql) {
        return BIG;
    }
    if (ql <= l && r <= qr) {
        return mn[i];
    }
    int mid = (l + r) / 2;
    return min(getmin(2 * i + 1, l, mid, ql, qr), getmin(2 * i + 2, mid, r, ql, qr));
}
 
void updpos(int i, int l, int r, int p, int val) {
    if (r - l == 1) {
        mn[i] = val;
        return;
    }
    int mid = (l + r) / 2;
    if (p < mid) {
        updpos(2 * i + 1, l, mid, p, val);
    } else {
        updpos(2 * i + 2, mid, r, p, val);
    }
    mn[i] = min(mn[2 * i + 1], mn[2 * i + 2]);
}
 
void push(int i, int l, int r) {
    mn[i] = min(mn[i], add[i]);
    if (r - l > 1) {
        add[2 * i + 1] = min(add[2 * i + 1], add[i]);
        add[2 * i + 2] = min(add[2 * i + 2], add[i]);
    }
    add[i] = BIG;
}
 
void updmin(int i, int l, int r, int ql, int qr, int x) {
    push(i, l, r);
    if (qr <= l || r <= ql) {
        return;
    }
    if (ql <= l && r <= qr) {
        add[i] = x;
        push(i, l, r);
        return;
    }
    int mid = (l + r) / 2;
    updmin(2 * i + 1, l, mid, ql, qr, x);
    updmin(2 * i + 2, mid, r, ql, qr, x);
    mn[i] = min(mn[2 * i + 1], mn[2 * i + 2]);
}
 
int getval(int i, int l, int r, int p) {
    push(i, l, r);
    if (r - l == 1) {
        return mn[i];
    }
    int mid = (l + r) / 2;
    if (p < mid) {
        return getval(2 * i + 1, l, mid, p);
    }
    return getval(2 * i + 2, mid, r, p);
}
 
class DSU {
public:
    DSU() = default;
 
    explicit DSU(int s) : par(vector<int>(s)), rg(vector<int>(s)) {
        iota(par.begin(), par.end(), 0);
    }
 
    int find(int p) {
        return (par[p] == p ? p : (par[p] = find(par[p])));
    }
 
    bool merge(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) {
            return False;
        }
        if (rg[x] > rg[y]) {
            swap(rg[x], rg[y]);
        }
        par[x] = y;
        if (rg[x] == rg[y]) {
            rg[y]++;
        }
        return True;
    }
 
private:
    vector<int> par;
    vector<int> rg;
};
 
int s[M], f[M], c[M], n, m, k;
vector<int> v[M], g[M];
vector<pair<int, int>> edges;
int order[M], spos[M], pos[M], h[M];
int mx[M], par[M], val[M], wpar[M];
int l[M], r[M], timer;
 
void dfs_span(int p, int last) {
    l[p] = timer++;
    par[p] = last;
    if (last == -1) {
        h[p] = 0;
    } else {
        h[p] = h[last] + 1;
    }
    order[k] = p;
    pos[p] = k;
    k++;
    for (int i : g[p]) {
        int to = p ^ s[i] ^ f[i];
        if (to != last) {
            wpar[to] = c[i];
            dfs_span(to, p);
        }
    }
    r[p] = timer;
}
 
int used[M], cnt_used;
 
void unite_way(DSU& cs, int x, int y) {
    int lca = -1;
    for (int cnt = 1; lca == -1; cnt += cnt) {
        int cx = x;
        int cy = y;
        cnt_used++;
        for (int i = 0; i < cnt; i++) {
            if (cx == -1) {
                break;
            }
            cx = cs.find(cx);
            used[cx] = cnt_used;
            cx = par[mx[cx]];
        }
        for (int i = 0; i < cnt && lca == -1; i++) {
            if (cy == -1) {
                break;
            }
            cy = cs.find(cy);
            if (used[cy] == cnt_used) {
                lca = cy;
                break;
            }
            cy = par[mx[cy]];
        }
    }
    vector<tuple<int, int, int>> merge_list;
    for (int i : vector<int>{x, y}) {
        while (True) {
            i = cs.find(i);
            if (i == lca) {
                break;
            }
            merge_list.emplace_back(mx[i], par[mx[i]], wpar[mx[i]]);
            i = par[mx[i]];
        }
    }
    for (const auto& t : merge_list) {
        int x = cs.find(get<0>(t));
        int y = cs.find(get<1>(t));
        int new_mx = mx[x];
        if (h[mx[y]] < h[mx[x]]) {
            new_mx = mx[y];
        }
        cs.merge(x, y);
        mx[cs.find(x)] = new_mx;
        val[cs.find(x)] = min(val[x], val[y]);
        val[cs.find(x)] = min(val[cs.find(x)], get<2>(t));
    }
}
 
vector<pair<int, int>> upd[M];
int ans[M];
 
void dfs_ans(int p, int last, int vmn, int vmx) {
    vector<pair<int, int>> pos;
    for (auto [val, i] : upd[p]) {
        pos.emplace_back(i, 0);
    }
    sort(pos.begin(), pos.end());
    pos.resize(unique(pos.begin(), pos.end()) - pos.begin());
    for (auto& t : pos) {
        t.second = getmin(0, 0, m, t.first, t.first + 1);
    }
    for (auto [val, i] : upd[p]) {
        updpos(0, 0, m, i, min(getmin(0, 0, m, i, i + 1), val));
    }
    if (last != -1) {
        ans[p] = edges[vmn].first + edges[vmx].first;
        ans[p] = min(ans[p], getmin(0, 0, m, vmx, m));
    }
    for (int i : g[p]) {
        int to = p ^ s[i] ^ f[i];
        if (to != last) {
            dfs_ans(to, p, min(vmn, spos[i]), max(vmx, spos[i]));
        }
    }
    for (auto [i, val] : pos) {
        updpos(0, 0, m, i, val);
    }
}
 
int go[M];
vector<int> in[M];
 
int main() {
#ifdef ONPC
    freopen("input", "r", stdin);
#endif
    ios::sync_with_stdio(false); cin.tie(); cout.tie();
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        cin >> s[i] >> f[i] >> c[i];
        s[i]--; f[i]--;
        v[s[i]].emplace_back(i);
        v[f[i]].emplace_back(i);
        edges.emplace_back(c[i], i);
    }
    sort(edges.begin(), edges.end());
    for (int i = 0; i < (int)edges.size(); i++) {
        if (i > 0 && edges[i].first == edges[i - 1].first) {
            spos[edges[i].second] = spos[edges[i - 1].second];
        } else {
            spos[edges[i].second] = i;
        }
    }
    DSU gr(n);
    for (auto [cval, i] : edges) {
        if (gr.merge(s[i], f[i])) {
            g[s[i]].emplace_back(i);
            g[f[i]].emplace_back(i);
        }
    }
    k = 0;
    dfs_span(0, -1);
    gr = DSU(n);
    DSU cs(n);
    for (int i = 0; i < n; i++) {
        mx[i] = i;
        val[i] = BIG;
    }
    for (int i = 0; i < n; i++) {
        go[i] = i;
        in[i].emplace_back(i);
    }
    build(0, 0, n);
    for (auto [cval, i] : edges) {
        bool is_s = (gr.find(s[i]) == gr.find(0));
        if (gr.merge(s[i], f[i])) {
            if (gr.find(s[i]) == gr.find(0)) {
                int x = s[i];
                if (is_s) {
                    x = f[i];
                }
                int cur_min = getval(0, 0, n, l[x]);
                if (cur_min != BIG) {
                    upd[x].emplace_back(cur_min + cval, spos[i]);
                }
                for (int p : in[go[x]]) {
                    if (val[cs.find(p)] != BIG) {
                        upd[mx[cs.find(p)]].emplace_back(val[cs.find(p)] + cval, spos[i]);
                    }
                }
            }
            if (in[go[s[i]]].size() > in[go[f[i]]].size()) {
                swap(s[i], f[i]);
            }
            int idx = go[s[i]];
            for (int x : in[idx]) {
                go[x] = go[f[i]];
                in[go[f[i]]].emplace_back(x);
            }
            in[idx].clear();
            go[s[i]] = go[f[i]];
            continue;
        }
        if (cs.find(s[i]) == cs.find(f[i])) {
            continue;
        }
        unite_way(cs, s[i], f[i]);
        int vertex = mx[cs.find(s[i])];
        updmin(0, 0, n, l[vertex], r[vertex], val[cs.find(s[i])]);
        if (gr.find(0) != gr.find(s[i])) {
            continue;
        }
        upd[vertex].emplace_back(val[cs.find(s[i])] + cval, spos[i]);
    }
    build(0, 0, m);
    dfs_ans(0, -1, BIG, 0);
    for (int i = 1; i < n; i++) {
        cout << ans[i] << "\n";
    }
    return 0;
}