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 }