Codeforces Round #628 (Div. 2) 一道比较中等的 树上构造 题。
题目链接:Codeforces 1325C。
系列题解:
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;
}
近期评论