思路
对于 Subtask 2,本质是确定了最小值,要使 \(1 \leadsto u\) 路径上边权最大值最小,显然直接上 Kruskal 重构树。
Code
#include <bits/stdc++.h>
#define re register
#define fst first
#define snd second
#define chmin(a,b) (a = min(a,b))
#define chmax(a,b) (a = max(a,b))using namespace std;typedef pair<int,int> pii;
const int N = 3e5 + 10,M = N * 2;
const int inf = 2e9 + 10;
int n,m;
bool mark[N];
vector<int> S[N];
vector<pii> g[N];
int tim,fp[N],sz[N],dfn[N],pid[N],dep[N],ltm[N],val[N];struct edge{int u,v,w;bool friend operator <(const edge &a,const edge &b){ return a.w < b.w; }
}E[N];inline int read(){int r = 0,w = 1;char c = getchar();while (c < '0' || c > '9'){if (c == '-') w = -1;c = getchar();}while (c >= '0' && c <= '9'){r = (r << 3) + (r << 1) + (c ^ 48);c = getchar();}return r * w;
}struct{int fp[N];inline void init(int n){for (re int i = 1;i <= n;i++) fp[i] = i;}inline int find(int x){if (fp[x] == x) return fp[x];else return fp[x] = find(fp[x]);}inline void merge(int a,int b){int x = find(a),y = find(b);fp[x] = y;}
}D;inline void dfs(int u,int fa){dep[u] = dep[fp[u] = fa] + 1;sz[pid[dfn[u] = ++tim] = u] = 1;for (pii v:g[u]){if (v.fst == fa) continue;ltm[v.fst] = max(ltm[u],v.snd);val[v.fst] = min(val[u],E[v.snd].w);dfs(v.fst,u); sz[u] += sz[v.fst];}
}struct{#define ls(u) (u << 1)#define rs(u) (u << 1 | 1)#define mid (tr[u].l + tr[u].r >> 1)int typ;struct node{int l,r;int val,tag;}tr[N << 2];inline void calc(int u,int k){ chmin(tr[u].val,k); chmin(tr[u].tag,k); }inline void pushup(int u){ tr[u].val = min(tr[ls(u)].val,tr[rs(u)].val); }inline void pushdown(int u){if (tr[u].tag < inf){ calc(ls(u),tr[u].tag); calc(rs(u),tr[u].tag); }tr[u].tag = inf;}inline void build(int u,int l,int r){tr[u] = {l,r,inf,inf};if (l == r) return (tr[u].val = (!typ ? val[pid[l]] : inf)),void();build(ls(u),l,mid); build(rs(u),mid + 1,r);pushup(u);}inline void modify(int u,int x,int k){if (tr[u].l == tr[u].r) return (tr[u].val = k),void();pushdown(u);if (x <= mid) modify(ls(u),x,k);else modify(rs(u),x,k);pushup(u);}inline void update(int u,int l,int r,int k){if (l <= tr[u].l && tr[u].r <= r) return calc(u,k);pushdown(u);if (l <= mid) update(ls(u),l,r,k);if (r > mid) update(rs(u),l,r,k);pushup(u);}inline int query(int u,int x){if (tr[u].l == tr[u].r) return tr[u].val;pushdown(u);if (x <= mid) return query(ls(u),x);else return query(rs(u),x);}#undef ls#undef rs#undef mid
}T1,T2;int main(){n = read(),m = read();fill(val + 1,val + n + 1,inf);for (re int i = 1,u,v,w;i <= m;i++){u = read(),v = read(),w = read();E[i] = {u,v,w};} sort(E + 1,E + m + 1);D.init(n);for (re int i = 1,u,v;i <= m;i++){u = E[i].u,v = E[i].v;if (D.find(u) == D.find(v)) continue;g[u].push_back({v,i});g[v].push_back({u,i});mark[i] = true; D.merge(u,v);// cerr << u << " " << v << " " << E[i].w << " ???\n";} dfs(1,0); D.init(n);T1.typ = 0,T2.typ = 1;T1.build(1,1,n); T2.build(1,1,n);for (re int i = 1;i <= n;i++) S[ltm[i]].push_back(i);for (re int i = 1,u,v,w;i <= m;i++){u = E[i].u,v = E[i].v,w = E[i].w;if (mark[i]){for (int x:S[i]) T2.modify(1,dfn[x],T1.query(1,dfn[x]) + w);}else{int x = D.find(u),y = D.find(v);if (x == y) continue;while (x != y){if (dep[x] < dep[y]) swap(x,y);int fa = D.find(fp[x]);chmin(val[fa],val[x]);D.merge(x,fa); x = fa;}T1.update(1,dfn[x],dfn[x] + sz[x] - 1,val[x]);T2.update(1,dfn[x],dfn[x] + sz[x] - 1,val[x] + w);}}for (re int i = 2;i <= n;i++) printf("%d\n",T2.query(1,dfn[i]));return 0;
}