C. Ehab and Path-etic MEXs
C. Ehab and Path-etic MEXs
- 对于成链的情况，\(\text{MEX} = n - 1\)
- 一般的，一定有一条路径包含0和1，则可以确定\(\text{MEX} \geq 2\)，观察发现，对于度数\(\geq 3\)的点，我们在他的三条边赋值为0, 1, 2使得其他路径的边有:
- 0,1,...
- 0,2,...
- 1,2,...
即一条路径上的边不能同时有0,1,2，使得\(\text{MEX} \leq 2\)，对其他边任意赋值即可
int n, ans[N];
vector<int> e[N];
void solve()
{
cin>>n;
for(int i = 1; i <= n - 1; i++)
{
int u, v; cin>>u>>v;
e[u].push_back(i);
e[v].push_back(i);
ans[i] = -1;
}
int vex = 0, cur = 0;
for(int i = 1; i <= n; i++)
if(e[i].size() >= 3)
vex = i;
for(auto &v : e[vex])
ans[v] = cur++;
for(int i = 1; i <= n - 1; i++)
{
if(ans[i] == -1)
ans[i] = cur++;
cout<<ans[i]<<endl;
}
return;
}