题意：给定一棵树所有的边，对所有的边进行标号，询问任意两点Mex的最大值最小的的标号方案（输出任何一种）。
Mex（u，v）表示从u到v的简单路径中没有出现的最小标号。
思路：（借鉴大佬的）
如果树是一条链，那么任何标号方案对首尾两端的 都不会影响，直接输出
到
即可；
其余情况可以证明 最大值的最小值一定为
：
（1）无论如何安排，标 边和标
边一定存在公共路径联通；
（2）对于非链的树一定存在 ，
的安排方式使得存在边不在
，
的任何公共路径上。在该边上标
即可满足不存在
，
，
的公共路径。
有两种比较简洁的实现方式：
（1）找到三个度为 的点，选取这三个点的临边，标为
，
，
，其余任意；
（2）找到一个度大于等于 的点，选取它的三个临边。
#include<bits/stdc++.h> const int maxn= 1e5+100; using namespace std; int a[maxn],b[maxn],num[maxn]; int main() { int n; scanf("%d",&n); for(int i=1;i<n;i++) { scanf("%d%d",&a[i],&b[i]); num[a[i]]++;num[b[i]]++; } int op = 0; for(int i=1;i<=n;i++) if(num[i]>=3) {op = i; break;} if(!op) for(int i=0;i<n-1;i++) printf("%d\n",i); else { for(int i=1,cnt1=0,cnt2=3;i<n;i++) { if((a[i]==op || b[i]==op) && cnt1<=2) printf("%d\n",cnt1++); else printf("%d\n",cnt2++); } } return 0; }
原文：https://www.cnblogs.com/mxw000120/p/13128517.html