vj-E题Ehab and Path-etic MEXs

Ehab and Path-etic MEXs

题意：给定一棵树所有的边，对所有的边进行标号，询问任意两点Mex的最大值最小的的标号方案（输出任何一种）。

Mex（u，v）表示从u到v的简单路径中没有出现的最小标号。

思路：（借鉴大佬的）

如果树是一条链，那么任何标号方案对首尾两端的 $MEX$ 都不会影响，直接输出 $0$ 到 $n-2$ 即可；

其余情况可以证明 $MEX(u,v)$ 最大值的最小值一定为 $2$ ：

（1）无论如何安排，标 $0$ 边和标 $1$ 边一定存在公共路径联通；

（2）对于非链的树一定存在 $0$ ， $1$ 的安排方式使得存在边不在 $0$ ， $1$ 的任何公共路径上。在该边上标 $2$ 即可满足不存在 $0$ ， $1$ ， $2$ 的公共路径。

有两种比较简洁的实现方式：

（1）找到三个度为 $1$ 的点，选取这三个点的临边，标为 $0$ ， $1$ ， $2$ ，其余任意；

（2）找到一个度大于等于 $3$ 的点，选取它的三个临边。

#include<bits/stdc++.h>

const int maxn= 1e5+100;

using namespace std;

int a[maxn],b[maxn],num[maxn];

int main()

{

    int n;

    scanf("%d",&n);

    for(int i=1;i<n;i++)

    {

        scanf("%d%d",&a[i],&b[i]);

        num[a[i]]++;num[b[i]]++;

    }

    int op = 0;

    for(int i=1;i<=n;i++) if(num[i]>=3) {op = i; break;}

    if(!op) for(int i=0;i<n-1;i++) printf("%d\n",i);

    else

    {

        for(int i=1,cnt1=0,cnt2=3;i<n;i++)

        {

            if((a[i]==op || b[i]==op) && cnt1<=2) printf("%d\n",cnt1++);

            else printf("%d\n",cnt2++);

        }

    }

    return 0;

}

巴特西

vj-E题Ehab and Path-etic MEXs

最新文章

热门文章