Ehab and Path-etic MEXs（思维题）

本文主要是介绍Ehab and Path-etic MEXs（思维题），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：

输入是一棵包含n个节点的树，包括n-1条边。编号为：0~n-2
问，如何给边编号，使得任意MEx(u,v)最小。
MEX(u,v)表示除了u - v路径上点的集合之外（0~n-2）的数中最小的数
这里有点绕，具体解释下。就是全部点的集合为：0~n-2 设为全集S
若设u~v途径的边的编号的集合为Q
则所求就是在全集S中求Q的补集中的最小值，使得这个数最小即可。

思路

1.所有节点度都不超过2的情况下，树是一条链，无论如何编号，都可行。
2.所存在接度大于2的情况，只需要找到一个度大于等于3的边，依次编号0，1，2即可
这样保证任意两个MEX(u,v)都是0，1，2中的一个。
理解清0，1，2的意义就可以理解清题意。

代码：

#include<stdio.h>
#include<string.h>
#define ll long long
const int N=1e5+10;
ll du[N],u[N],v[N];   //du记录度，u,v记录输入顺序
int n,sum,ans;    
int main()
{scanf("%d",&n);for(int i=1;i<n;i++){    //统计每结点的度scanf("%lld%lld",&u[i],&v[i]);du[u[i]]++;du[v[i]]++;}int flag=0;     //判读是否有度大于2的节点for(int i=1;i<=n;i++){if(du[i]>2){flag=i;break;  //记录该接待你出现在第几项}}if(!flag){    //没有则说明全图是一张链for(int i=0;i<n-1;i++)printf("%d\n",i);}else{ans=0,sum=3;for(int i=1;i<n;i++){if((u[i]==flag||v[i]==flag)&&ans<3){      //把标记的的地方依次放上0，1，2，其余随意printf("%d\n",ans++);}elseprintf("%d\n",sum++);}}return 0;
}

这篇关于Ehab and Path-etic MEXs（思维题）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---