题面
Description
给定一个\(n\)个点\(m\)条边的连通图，保证没有自环和重边。对于每条边求出,在其他边权值不变的情况下,它能取的最大权值，使得这条边在连通图的所有最小生成树上。假如最大权值为无限大，则输出\(-1\)。
Input
第一行两个整数\(n\),\(m\)，表示\(n\)个点\(m\)条边
接下来\(m\)行，每行\(3\)个整数\(x\),\(y\),\(z\)，表示节点\(x\)和节点\(y\)之间有一条长\(z\)的边。
Output
输出一行\(m\)个整数，表示每条边的答案
Sample Input
4 4
1 2 2
2 3 2
3 4 2
4 1 3
Sample Output
2 2 2 1
HINT
对于\(30\%\)的数据\(1≤n≤10^3\),\(1≤m≤3\times10^3\)
对于\(100\%\)的数据\(1≤n,m≤2\times 10^5\),\(1≤z≤10^9\)
题解
（来自XSY的solution）
先求出图的一棵最小生成树：
对于不在树上的边\((x,y)\)， 它的权值只要小于树上\(x\)到\(y\)路径中一条边就可以代替这条边。
对于在树上的边\((x,y)\)，可以先预处理出所有两端在\(x\)到\(y\)路径上的不在树上的边的最小值。它的权值一定要小于最小值。
路径\(max\)和\(min\)都可以用倍增求。
时间复杂度\(O(nlogn)\)。
代码：
#include<bits/stdc++.h>
#define N 200010
#define M127 2139062143
using namespace std;
struct edge
{
int u,v,w,id;
}e[N];
int n,m,fa[N],ans[N];
int cnt,head[N],to[N<<1],nxt[N<<1],w[N<<1],id[N<<1];
int f[N][20],maxn[N][20],from[N],d[N];
bool flag[N];
void adde(int u,int v,int wi,int idi)
{
to[++cnt]=v;
w[cnt]=wi;
id[cnt]=idi;
nxt[cnt]=head[u];
head[u]=cnt;
}
bool cmp(edge a,edge b)
{
return a.w<b.w;
}
int find(int x)
{
if(fa[x]!=x)
return fa[x]=find(fa[x]);
return x;
}
void dfs(int u)
{
for(int i=1;i<=18;i++)
{
f[u][i]=f[f[u][i-1]][i-1];
maxn[u][i]=max(maxn[u][i-1],maxn[f[u][i-1]][i-1]);
}
for(int i=head[u];i;i=nxt[i])
{
if(to[i]!=f[u][0])
{
f[to[i]][0]=u;
maxn[to[i]][0]=w[i];
from[to[i]]=id[i];
d[to[i]]=d[u]+1;
dfs(to[i]);
}
}
}
int getMax(int a,int b,int &lca)
{
int ans=0;
if(d[a]<d[b])
swap(a,b);
for(int i=18;i>=0;i--)
{
if(d[f[a][i]]>=d[b])
{
ans=max(ans,maxn[a][i]);
a=f[a][i];
}
}
if(a==b)
{
lca=a;
return ans;
}
for(int i=18;i>=0;i--)
{
if(f[a][i]!=f[b][i])
{
ans=max(ans,maxn[a][i]);
ans=max(ans,maxn[b][i]);
a=f[a][i],b=f[b][i];
}
}
lca=f[a][0];
return max(ans,max(maxn[a][0],maxn[b][0]));
}
void solve(int u,int lca,int wi)
{
u=find(u);
while(d[u]>d[lca])
{
ans[from[u]]=min(ans[from[u]],wi-1);
fa[u]=find(f[u][0]);
u=find(u);
}
}
int main()
{
memset(ans,127,sizeof(ans));
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
fa[i]=i;
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
e[i].id=i;
}
sort(e+1,e+m+1,cmp);
for(int i=1,tot=0;i<=m;i++)
{
if(tot==n-1)
break;
int x=find(e[i].u);
int y=find(e[i].v);
if(x!=y)
{
fa[y]=x;
adde(e[i].u,e[i].v,e[i].w,e[i].id);
adde(e[i].v,e[i].u,e[i].w,e[i].id);
flag[i]=true;
tot++;
}
}
dfs(1);
for(int i=1;i<=n;i++)
fa[i]=i;
for(int i=1;i<=m;i++)
{
if(!flag[i])
{
int lca;
ans[e[i].id]=getMax(e[i].u,e[i].v,lca)-1;
solve(e[i].u,lca,e[i].w);
solve(e[i].v,lca,e[i].w);
}
}
for(int i=1;i<=m;i++)
{
if(ans[i]==M127)printf("-1 ");
else printf("%d ",ans[i]);
}
return 0;
}