传送门 题解：先求出最小生成树，用倍增LCA求出不在最小生成树中的边的答案，同时再用这个答案它去更新最小生成树中的边的答案。为了提高更新这一操作的效率，枚举有序（从小到大）的边集，更新过的用并查集连在一起（由于从小到大，小的最优，下条边一定不会再次更新它们），下一次直接往上跳即可。
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; const int MAXN=2e5+2,INF=0x3f3f3f3f; struct kruskal { int u,v,w,id; friend bool operator <(const kruskal &a,const kruskal &b) { return a.w<b.w; } }kr[MAXN]; int head[MAXN],edge; struct EDGE { int v,nxt,w,id; }e[MAXN<<1]; bool inm[MAXN]; int n,m; int fa[MAXN]; int ans[MAXN]; int anc[MAXN][19],mx[MAXN][19],dep[MAXN],up[MAXN]; inline int read() { int x=0;char c=getchar(); while (c<'0'||c>'9') c=getchar(); while (c>='0'&&c<='9') x=x*10+c-'0',c=getchar(); return x; } inline void adde(int u,int v,int w,int id) { e[edge].nxt=head[u],e[edge].v=v,e[edge].id=id,e[edge].w=w,head[u]=edge++; e[edge].nxt=head[v],e[edge].v=u,e[edge].id=id,e[edge].w=w,head[v]=edge++; } int find(int x) { return fa[x]==x?x:fa[x]=find(fa[x]); } void dfs(int p,int f,int d) { dep[p]=dep[f]+1,anc[p][0]=f,mx[p][0]=d; for (int i=1;i<=18;++i) anc[p][i]=anc[anc[p][i-1]][i-1],mx[p][i]=max(mx[p][i-1],mx[anc[p][i-1]][i-1]); for (int i=head[p];~i;i=e[i].nxt) { int v=e[i].v; if (v==f) continue; up[v]=e[i].id,dfs(v,p,e[i].w); } } int lca(int x,int y,int &d) { d=0;if (dep[x]<dep[y]) x^=y^=x^=y; for (int i=18;i>=0;--i) { if (dep[anc[x][i]]>=dep[y]) { d=max(d,mx[x][i]); x=anc[x][i]; } } if (x==y) return x; for (int i=18;i>=0;--i) { if (anc[x][i]^anc[y][i]) { d=max(d,max(mx[x][i],mx[y][i])); x=anc[x][i],y=anc[y][i]; } } d=max(d,max(mx[x][0],mx[y][0])); return anc[x][0]; } void modify(int x,int lca,int w) { x=find(x); while (dep[x]>dep[lca]) { ans[up[x]]=min(ans[up[x]],w); int y=find(anc[x][0]); fa[x]=y; x=find(x); } } int main() { // freopen("codeforces 827D.in","r",stdin); while (~scanf("%d%d",&n,&m)) { memset(head,-1,sizeof(head)); memset(inm,0,sizeof(inm)); edge=0; for (register int i=1;i<=n;++i) fa[i]=i; for (register int i=1;i<=m;++i) kr[i].id=i,kr[i].u=read(),kr[i].v=read(),kr[i].w=read(); sort(kr+1,kr+m+1); int blo=n; for (register int i=1;i<=m&&blo>1;++i) { int u=kr[i].u,v=kr[i].v; u=find(u),v=find(v); if (u^v) { fa[u]=v,inm[i]=true,--blo; adde(kr[i].u,kr[i].v,kr[i].w,kr[i].id); } } dfs(1,0,0); memset(ans,INF,sizeof(ans)); for (register int i=1;i<=n;++i) fa[i]=i; for (register int i=1;i<=m;++i) { if (inm[i]) continue; int u=kr[i].u,v=kr[i].v,f=lca(u,v,ans[kr[i].id]); --ans[kr[i].id]; modify(u,f,kr[i].w-1); modify(v,f,kr[i].w-1); } for (int i=1;i<=m;++i) printf("%d\n",ans[i]==INF?-1:ans[i]); } return 0; }