CF1325C Ehab and Path-etic MEXs 题解

题目链接：CF1325C Ehab and Path-etic MEXs

题意：

给定一个 \(n\) 个节点 \(n-1\) 条边的树

要求给边重新标注边权

分别为 \(0,1,2...n-2\) 。

然后使得树上任意两点 \(u,v\) 的 \(\mathrm{MEX}(u,v)\) 的最大值最小。

\(\mathrm{MEX}(u,v)\) 是 \(u\) 到 \(v\) 的简单路径没有出现的自然数中最小的数。

输入格式：

The first line contains the integer \(n (2 \le n \le 10^5)\) — the number of nodes in the tree.

Each of the next \(n-1\) lines contains two space-separated integers \(u\) and \(v\) \(( 1 \le u,v \le n )\) that mean there's an edge between nodes \(u\) and \(v\) . It's guaranteed that the given graph is a tree.

输出格式：

Output \(n-1\) integers. The \(i^{th}\) of them will be the number written on the \(i^{th}\) edge (in the input order).

注意到无论怎么构造，\(0,1\) 总归在一条链上。

所以只要找到一个度数大于三的，把 \(0,1,2\) 放在分叉位置就好了

时间复杂度 \(\mathcal{O}(n)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(5e5+15))

vector<int> vec[N];
int n,pos=1,o,a[N],in[N];
void add(int u,int v) { vec[u].push_back(v); ++in[u]; }
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n;
    for(int i=1,u,v; i<n; i++) { cin >> u >> v; add(u,i); add(v,i); }
    int mx = *max_element(in, in + n);
    if(mx < 3){ for(int i=0; i<n-1; i++) cout << i << '\n'; return 0; }
    for(int i=1; i<=n; i++)
        if(in[i] >= 3) { for(int j=0; j<3; j++) a[vec[i][j]] = ++o; break; }
    for(int i=1; i<n; i++) if(!a[i]) a[i] = ++o;
    for(int i=1; i<n; i++) cout << a[i] - 1 << '\n';
    return 0;
}