Codeforces Round #628 (Div. 2)C. Ehab and Path-etic MEXs（构造+树）

题目链接：https://codeforces.com/contest/1325/problem/C

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

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

题目思路：根据大佬的说法（大佬原话），只要有一个点的度数大于2，那么三个出边分别连0、1、2就可以了，身下的随便连，因为这样的话，任何一个Mex（u，v）值是一定一定是不大于2的，不可能有一个路径同时走0、1、2这三天边。本来思路大体是对的，太菜不会建图、吐了。不过建出来可能也要wa一阵子。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 vector<int> v[100005];
 4 int ans[100005];
 5 int main()
 6 {
 7     int n;
 8     scanf("%d",&n);
 9     for (int i=1;i<n;i++)
10     {
11         int a,b;
12         scanf("%d%d",&a,&b);
13         v[a].push_back(i);
14         v[b].push_back(i);
15         ans[i]=-1;
16     }
17     pair<int,int> mx(0,0);
18     for (int i=1;i<=n;i++)
19     mx=max(mx,make_pair((int)v[i].size(),i));
20     int cur=0;
21     for (int i:v[mx.second])
22     ans[i]=cur++;
23     for (int i=1;i<n;i++)
24     {
25         if (ans[i]==-1)
26         ans[i]=cur++;
27         printf("%d
",ans[i]);
28     }
29 }