题目要求每条边的权值最大值使得其必定出现在最小生成树上。
CF 上唯一一道有 LCT tag 的题。
那么可以先模拟一遍 Kruskal，可以看到有一条边，端点为 ，如果：
-
已经在一个连通块内，那么只有它的边权小于 路径上某一条边才能加入。
-
不在一个连通块内，那么直接加入生成树即可。
对于 1，也就是非树边，很明显它的答案是 路径上边权最大值 -1。可以用 LCT 维护，当然你也可以先把 MST 建出来，然后树剖或倍增。
非树边处理了，那么树边呢？
对于一条非树边，其连接了 ，边权为 ，那么 路径上所有的边权应都小于 ，防止这条非树边上位替换它。
那么可以树剖，用线段树查询一个区间 min。
我用的是一种类似差分的做法。
还是这条连接了 的非树边，求出它们的 ，然后搞 个优先队列，把 和 插入 和 中，跑一边 dfs，合并每个点的儿子的优先队列，顺便把 在该点下方的踢出（记得用启发式，不然会 T 爆）。那么处理完后的队首即为答案。
最后还要注意下队列是否为空。
常数巨大，成功名列最劣解。
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+500;
int v[N],a[N],ch[N][2],rev[N],f[N],ans[N],dep[N],head[N],cnt,top,fa[N][20],opt[N][3];
struct node
{
int u,v,w,id,nxt;
friend bool operator<(node a,node b)
{
return a.w<b.w;
}
}edge[N],e[N<<1];
#define ls ch[x][0]
#define rs ch[x][1]
int isroot(int x){return ch[f[x]][0]==x|ch[f[x]][1]==x;}
void up(int x){v[x]=max(max(v[ls],v[rs]),a[x]);}
void reversal(int x){swap(ls,rs);rev[x]^=1;}
void down(int x){if(!rev[x])return;reversal(ls),reversal(rs);rev[x]=0;}
void rotate(int x)
{
int y=f[x],z=f[y],k=(ch[y][1]==x),w=(ch[z][1]==y),an=ch[x][k^1];
if(isroot(y))ch[z][w]=x;ch[x][k^1]=y;ch[y][k]=an;
if(an)f[an]=y;f[y]=x,f[x]=z;
up(y);up(x);
}
int st[N];
void splay(int x)
{
int y=x,z=0;
st[++z]=x;
while(isroot(y))st[++z]=y=f[y];
while(z)down(st[z--]);
while(isroot(x))
{
y=f[x],z=f[y];
if(isroot(y))rotate((ch[y][1]==x)^(ch[z][1]==y)?x:y);
rotate(x);
}
up(x);
}
void access(int x){for(int y=0;x;x=f[y=x])splay(x),rs=y,up(x);}
void make_root(int x){access(x);splay(x);reversal(x);}
int find_root(int x){access(x);splay(x);while(ls)down(x),x=ls;splay(x);return x;}
void split(int x,int y){make_root(x);access(y);splay(y);}
void link(int x,int y){make_root(x);if(find_root(y)!=x)f[x]=y;}
void cut(int x,int y){make_root(x);if(find_root(y)==x&&f[y]==x&&!ch[y][0])f[y]=rs=0,up(x);}
int n,m;
char cch,B0[1<<15],*S=B0,*T=B0;
#define getc() (S==T&&(T=(S=B0)+fread(B0,1,1<<15,stdin),S==T)?0:*S++)
int aa;int read(){
while(cch=getc(),cch<'0'||cch>'9');aa=cch-'0';
while(cch=getc(),cch>='0'&&cch<='9')aa=((aa<<3)+(aa<<1))+cch-'0';return aa;
}
void add(int u,int v)
{
e[++cnt].u=u;
e[cnt].v=v;
e[cnt].nxt=head[u];
head[u]=cnt;
}
void dfs(int x,int ff)
{
fa[x][0]=ff;dep[x]=dep[ff]+1;
for(int i=1;i<=19;i++)
{
if(!fa[fa[x][i-1]][i-1])break;
fa[x][i]=fa[fa[x][i-1]][i-1];
}
for(int i=head[x];i;i=e[i].nxt)
{
int v=e[i].v;
if(v==ff)continue;
dfs(v,x);
}
}
int LCA(int x,int y)
{
if(dep[y]>dep[x])swap(x,y);
for(int i=19;i>=0;i--)if(dep[x]-(1<<i)>=dep[y])x=fa[x][i];
if(y==x)return x;
for(int i=19;i>=0;i--)if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];
return fa[x][0];
}
struct priority
{
int v,p;
friend bool operator<(priority a,priority b)
{
return a.v>b.v;
}
};
priority_queue<priority>q[N];
void dfs2(int x)
{
for(int i=head[x];i;i=e[i].nxt)
{
int v=e[i].v;
if(v==fa[x][0])continue;
dfs2(v);
if(q[v].size()>q[x].size())swap(q[v],q[x]);
while(!q[v].empty())
{
if(dep[q[v].top().p]<=dep[x])q[x].push(q[v].top());
q[v].pop();
}
}
while(q[x].size()&&dep[q[x].top().p]>dep[x])q[x].pop();
if(x>n&&q[x].size())ans[x-n]=q[x].top().v;
}
main()
{
cin>>n>>m;
for(int i=1;i<=m;i++)cin>>edge[i].u>>edge[i].v>>edge[i].w,edge[i].id=i,ans[i]=-1;
sort(edge+1,edge+1+m);
for(int i=1;i<=m;i++)
{
int x=edge[i].u,y=edge[i].v;a[edge[i].id+n]=edge[i].w;
if(find_root(x)==find_root(y))
{
split(x,y);
ans[edge[i].id]=v[y]-1;
opt[++top][0]=x;opt[top][1]=y;opt[top][2]=edge[i].w-1;
}
else
{
link(x,edge[i].id+n);
link(y,edge[i].id+n);
add(x,edge[i].id+n);add(edge[i].id+n,x);
add(y,edge[i].id+n);add(edge[i].id+n,y);
}
}
dfs(1,0);
for(int i=1;i<=top;i++)
{
int x=opt[i][0],y=opt[i][1],lca=LCA(x,y);
if(x!=lca)q[x].push((priority){opt[i][2],lca});
if(y!=lca)q[y].push((priority){opt[i][2],lca});
}
dfs2(1);
for(int i=1;i<=m;i++)cout<<ans[i]<<' ';
}
写的可能有些臭？
