[题解]CF827D Best Edge Weight

题目描述
给定一个点数为 $n$ ，边数为 $m$ ，权值不超过 $10^9$ 的带权连通图，没有自环与重边。
现在要求对于每一条边求出，这条边的边权最大为多少时，它还能出现在所有可能的最小生成树上，如果对于任意边权都出现，则输出 $-1$ 。 ( $2 \leq n \leq 2 \times 10^5, n - 1 \leq m \leq 2 \times 10^5$ ）

$Solution$
建出最小生成树
讨论这条边 $(x,y)$ 在不在最小生成树上

$1$ 若不在那么在 $(x,y)$ 这条链上应该有边比它小，所以等于 $(x,y)$ 链上最大边权 $-1$
$2$ 若在那么它应该比所有经过 $(x,y)$ 这条边的非树边小
因为如果一条链经过 $(x,y)$ ，那么它就有机会替代 $(x,y)$
第一种我们直接树上倍增
第二种求经过 $(x,y)$ 的最大数，设为 $v$ ,可以树链剖分 $O(n log ^ 2 n)$
也可以将链从小到大排序，先覆盖的就不用改了
那么，我们用并查集实现这个合并
每次加入一条链 $(x,y)$ ，设 $x,y$ 的 $LCA$ 为 $o$
也就是说，我们将 $x$ 到 $o$ ， $y$ 到 $o$ 合并，标记他们的值 $v[i]$
我们每次从 $x$ 跳到 $getfather(x)$ 上
因为合并过，所有它们的 $v$ 值已被确定，不用再修改
所以我们只用将 $v[getfather(x)]$ 修改，注意边权下放到点
然后将 $getfather(x)$ 和 $father[getfather(x)]$ 合并
复杂度 $O(n log n)$ ，因为每个点只会被合并一次

$Code$

#include <bits/stdc++.h>
#define ri register int
#define ll long long
using namespace std;
const int Maxn=5e5;
const int Lgn=20;
const int Maxm=2e6;
const int Inf=1e9+1;
struct Edge {
    int x,y,z,id;
}e[Maxm+5];
int lt[Maxn+5],nt[2*Maxn+5],ed[2*Maxn+5],val[2*Maxn+5],cnt;
int st[Maxn+5][Lgn+5],mx[Maxn+5][Lgn+5];
int father[Maxn+5],size[Maxn+5],son[Maxn+5],dep[Maxn+5],top[Maxn+5],dfn[Maxn+5],vt;
int link[Maxm+5],mark[Maxm+5],v[Maxn+5],n,m;
bool cmp(Edge a,Edge b) {
    return a.z<b.z;
}
void addedge(int x,int y,int z) {
    ed[++cnt]=y;nt[cnt]=lt[x];lt[x]=cnt;
    val[cnt]=z;
}
int getfather(int v) {
    return father[v]==v?v:father[v]=getfather(father[v]);
}
void dfs1(int u,int fa) {
    dep[u]=dep[fa]+1;st[u][0]=fa;
    int t=ceil(log2(dep[u]));
    for(ri i=1;i<=t;i++) {
        st[u][i]=st[st[u][i-1]][i-1];
        mx[u][i]=max(mx[u][i-1],mx[st[u][i-1]][i-1]);
    }
    size[u]=1;
    int maxn=0;
    for(ri i=lt[u];i;i=nt[i]) {
        int v=ed[i];
        if(v!=fa) {
            mx[v][0]=val[i];
            dfs1(v,u);
            if(size[v]>maxn)maxn=size[v],son[u]=v;
            size[u]+=size[v];    
        }
    }
}
void dfs2(int u,int fa,int tp) {
    top[u]=tp;dfn[u]=++vt;
    if(son[u])dfs2(son[u],u,tp);
    for(ri i=lt[u];i;i=nt[i]) {
        int v=ed[i];
        if(v!=fa&&v!=son[u])dfs2(v,u,v);
    }
}
int lca(int x,int y) {
    while(top[x]!=top[y]) {
        if(dep[top[x]]<dep[top[y]])swap(x,y);
        x=st[top[x]][0];
    }
    if(dep[x]>dep[y])swap(x,y);
    return x;
}
void modify(int x,int y,int z) {
    int o=lca(x,y);
    while(1) {
        x=getfather(x);
        if(dep[x]<=dep[o])break;
        v[x]=z;
        father[x]=st[x][0],x=getfather(x);
    }
    while(1) {
        y=getfather(y);
        if(dep[y]<=dep[o])break;
        v[y]=z;
        father[y]=st[y][0],y=getfather(y);
    }
}
int getmax(int x,int y) {
    int o=lca(x,y);
    int depx=ceil(log2(dep[x])),mx1=0;
    for(ri i=depx;i>=0;i--)
        if(dep[st[x][i]]>dep[o]) {
            mx1=max(mx1,mx[x][i]);
            x=st[x][i];
        }
    if(x!=o)mx1=max(mx1,mx[x][0]);
    int depy=ceil(log2(dep[y])),mx2=0;
    for(ri i=depy;i>=0;i--)
        if(dep[st[y][i]]>dep[o]) {
            mx2=max(mx2,mx[y][i]);
            y=st[y][i];
        }
    if(y!=o)mx2=max(mx2,mx[y][0]);
    return max(mx1,mx2);
}
void kruskal() {
    sort(e+1,e+m+1,cmp);
    for(ri i=1;i<=n;i++)father[i]=i;
    for(ri i=1;i<=m;i++) {
        link[e[i].id]=i;
        int x=getfather(e[i].x),y=getfather(e[i].y);
        if(x!=y) {
            addedge(e[i].x,e[i].y,e[i].z);
            addedge(e[i].y,e[i].x,e[i].z);
            father[y]=x;
            mark[e[i].id]=1;
        }
    }
}
int main() {
    scanf("%d%d",&n,&m);
    for(ri i=1;i<=m;i++)scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].z),e[i].id=i;
    kruskal();
    dfs1(1,0);
    dfs2(1,0,1);
    for(ri i=1;i<=n;i++)father[i]=i,v[i]=Inf;
    for(ri i=1;i<=m;i++)
        if(!mark[e[i].id])modify(e[i].x,e[i].y,e[i].z);
    for(ri i=1;i<=m;i++) {
        int s=link[i];
        if(mark[i]) {
            int u=dep[e[s].x]>dep[e[s].y]?e[s].x:e[s].y;
            int ans=v[u];
            printf("%d\n",ans==Inf?-1:ans-1);
        }
        else {
            int ans=getmax(e[s].x,e[s].y);
            printf("%d\n",ans-1);
        }
    }
    return 0;
}