NOIP2023模拟2联测23 害怕

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

题目大意

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

你要给这些边赋上边权，要求边权是 $1\sim m$ 的序列，使得蓝色的边是最小生成树。

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

$1\leq n,m\leq 5\times 10^5,m\geq n-1$

题解

一个图的一棵树是最小生成树，当且仅当任意的非树边的边权都比与其形成环的树边大。

要让字典序最小，也就是要在蓝边形成最小生成树的前提下，让编号小的边尽量小。

我们按编号从小到大枚举边：

如果是树边，且该边没有被赋值，则直接将其赋值
如果是非树边，则将与其形成环的树边按编号从小到大赋值，再给这条非树边赋值

求与非树边形成环的树边，其实就是求非树边的两个点在树边上的路径。那么，给与非树边形成环的树边其实就是在树上一边求 $l c a$ 一边给边赋值。

注意赋值是从小到大赋值，这样才能保证字典序最小。

在赋值的时候，每赋值完一条树边，我们可以用并查集来将树边上的两个点并起来，每次向上跳时只要到当前所在的并查集的编号最小的点，然后给这个点到父亲的边赋值即可。

但是，这样的话，它们有可能跳到 $l c a$ 上面的点。但这其实不影响，因为当两个点跳到同一个位置时就不会再跳了（也就是第一次跳到 $l c a$ 或 $l c a$ 的祖先时就不会再跳了），所以就不会对 $l c a$ 上面的边赋值。

因为用了并查集，所以我们可以暴力跳，每条边最多只会被跳一次，时间复杂度平摊下来是 $O (n)$ 的。在将树边按编号从小到大赋值时要对树边排序，总时间复杂度是 $O(n\log n)$ 的。

所以，总时间复杂度为 $O(n\log n)$ 。

code

#include<bits/stdc++.h>
using namespace std;
const int N=500000;
int n,m,now=0,tot=0,d[2*N+5],l[2*N+5],r[N+5],id[2*N+5];
int fa[N+5],dep[N+5],tf[N+5],dn[N+5],up[N+5],ans[N+5];
struct node{int x,y,z;
}w[N+5];
void add(int xx,int yy,int i){l[++tot]=r[xx];d[tot]=yy;r[xx]=tot;id[tot]=i;
}
void dfs(int u,int f){fa[u]=f;dep[u]=dep[f]+1;tf[u]=u;for(int i=r[u];i;i=l[i]){if(d[i]==f) continue;dn[id[i]]=d[i];up[d[i]]=id[i];dfs(d[i],u);}
}
int find(int ff){if(ff!=tf[ff]) tf[ff]=find(tf[ff]);return tf[ff];
}
void pt(int x,int y){vector<int>v;x=find(x);y=find(y);while(x!=y){if(dep[x]<dep[y]) swap(x,y);v.push_back(up[x]);tf[x]=find(fa[x]);x=tf[x];}sort(v.begin(),v.end());for(int i=0;i<v.size();i++){ans[v[i]]=++now;}
}
int main()
{scanf("%d%d",&n,&m);for(int i=1,x,y,z;i<=m;i++){scanf("%d%d%d",&x,&y,&z);w[i]=(node){x,y,z};if(z){add(x,y,i);add(y,x,i);}}dfs(1,0);for(int i=1;i<=m;i++){if(w[i].z){if(tf[dn[i]]==dn[i]){ans[i]=++now;tf[dn[i]]=find(fa[dn[i]]);}}else{pt(w[i].x,w[i].y);ans[i]=++now;}}for(int i=1;i<=m;i++){printf("%d ",ans[i]);}return 0;
}