NOIP2023模拟2联测23-害怕

本文主要是介绍NOIP2023模拟2联测23-害怕，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

澪有个 $n$ 个点 $m$ 条边的无向图，每条边都有蓝白两种颜色中的一种，保证蓝色的边形成了这个图的一个生成树。

她希望给这些边赋上边权，保证边权是 $\sim m$ 的排列，使得蓝色的边是最小生成树。

希望这些边权形成的序列字典序最小，也就是先比较第一条边的边权，再比较第二条边的边权，依次类推。

$n,m\le5\times10^5$

对于一个生成树是最小生成树，都有任意的非树边的边权都与其形成环的树边的边权大。

一种想法是：考虑按输入顺序贪心确定每条边权值，对于一条非树边，记 $k$ 为与之形成环的未被确定权值的树边数量，给这 $k$ 条边按顺序确定权值，再给这条非树边设权值；对于树边直接赋权值即可。（正确性显然）

这样做时间复杂度是 $O (nm)$ ，考虑优化。注意到每次操作时被标记的树边是连续的，所以可以用并查集维护这个连通块深度最小的点，每次像树剖找 LCA 选最深的点往上跳到所在连通块的顶端，直到两个点属于一个连通块为止。由于用了并查集维护，每条边只会走一次，后面又排序，时间复杂度 $O(n\log n)$ 。

具体实现看代码

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+1;
int n,m,f[N],val[N],p[N],ans[N],cnt1;
int head[N],nxt[N<<1],to[N<<1],w[N<<1],cnt;
int dep[N],fa[N],sz[N],son[N],top[N];
struct node
{int u,v,id,type;
}a[N];
void add(int u,int v,int W)
{to[++cnt]=v;w[cnt]=W;nxt[cnt]=head[u];head[u]=cnt;
}
void dfs(int u,int f)
{fa[u]=f;dep[u]=dep[f]+1;for(int i=head[u];i;i=nxt[i]){if(to[i]!=f){val[to[i]]=w[i];dfs(to[i],u);}}
}
int find(int x)
{return x==f[x]?x:f[x]=find(f[x]);
}
int main()
{scanf("%d%d",&n,&m);for(int i=1;i<=m;i++){scanf("%d%d%d",&a[i].u,&a[i].v,&a[i].type);if(a[i].type) add(a[i].u,a[i].v,i),add(a[i].v,a[i].u,i);}for(int i=1;i<=n;i++) f[i]=i;dfs(1,0);for(int i=1;i<=m;i++){int x=a[i].u,y=a[i].v,cnt=0;while(find(x)!=find(y)){if(dep[find(x)]<dep[find(y)]) swap(x,y);x=find(x);f[x]=find(fa[x]);p[++cnt]=val[x];}sort(p+1,p+1+cnt);for(int j=1;j<=cnt;j++) ans[p[j]]=++cnt1;if(a[i].type==0) ans[i]=++cnt1;}for(int i=1;i<=m;i++) printf("%d ",ans[i]);
}