Codeforces Round #628 (Div. 2) 一道比较中等的 树上构造 题。

题目链接：Codeforces 1325C。

[toc]

系列题解：
1. 「题解」Codeforces Round #628 (Div. 2) A EhAb AnD gCd；
2. 「题解」Codeforces Round #628 (Div. 2) B CopyCopyCopyCopyCopy；
3. 「题解」Codeforces Round #628 (Div. 2) C Ehab and Path-etic MEXs；
4. 「题解」Codeforces Round #628 (Div. 2) D Ehab the Xorcist；
5. 「题解」Codeforces Round #628 (Div. 2) E Ehab’s REAL Number Theory Problem；
6. 「题解」Codeforces Round #628 (Div. 2) F Ehab’s Last Theorem。

题目

原题

题意简述

给出一个节点数为 $n$ 的树，将树上的每条边都附上一个各不相同的边权 $\omega\in[0,n-2]$，你要使得 $\forall u,v\in[1,n]\operatorname{mex}(u,v)$ 的最大值最小。

数据范围

$$2\leq n\leq 10^5$$

时空限制

见原题 pdf 文件。

题解

思路

考虑树退化为链的情况，发现 $\operatorname{mex}(u,v)$ 取到最大值当且仅当 $u,v$ 是链的两个端点，所以最大值恒为 $n-1$，随便填即可。

考虑一般树的情况，发现

对于度数大于等于 $3$ 的点，随便将与它相连的三条边赋值为 $0,1,2$，那么对于每一颗子树内部，$\operatorname{mex}()$ 的值为 $0$，因为边权一定各不相同，跨 $0,2$ 边的 $\operatorname{mex}()$ 的值为 $1$，同理，最终的 $\operatorname{mex}()$ 的最大值为 $2$。

其他的边权随便填就好了。

代码

为了方便，可以把边权全部加上一，最后输出时再减掉即可。

#include<bits/stdc++.h>
using namespace std;
#define reg register
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
static char buf[100000],*p1=buf,*p2=buf;
inline int read(void){
    reg bool f=false;
    reg char ch=getchar();
    reg int res=0;
    while(ch<'0'||'9'<ch)f|=(ch=='-'),ch=getchar();
    while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar();
    return f?-res:res;
}

const int MAXN=100000+5;

int n;
int Deg[MAXN];
vector<int> V[MAXN]; //用 vector 存节点连接的边的编号
int ans[MAXN];

int main(void){
    n=read();
    for(int i=1;i<n;++i){
        static int u,v;
        u=read(),v=read();
        ++Deg[u];
        ++Deg[v];
        V[u].push_back(i);
        V[v].push_back(i);
    }
    reg bool flag=false;
    reg int pos=-1;
    for(reg int i=1;i<=n;++i){
        if(Deg[i]>=3){
            flag=true;
            pos=i;
            break;
        }
    }
    if(flag){
        ans[V[pos][0]]=1;
        ans[V[pos][1]]=2;
        ans[V[pos][2]]=3;
        reg int cnt=3;
        for(reg int i=1;i<n;++i)
            if(ans[i])
                printf("%d\n",ans[i]-1);
            else
                printf("%d\n",++cnt-1);
    }
    else{
        reg int cnt=0;
        for(reg int i=1;i<n;++i)
            printf("%d\n",++cnt-1);
    }
    return 0;
}