Ehab and Path-etic MEXs CodeForces - 1325C

原题链接
考察:构造
思路:
??求所有构造图内任意两点Mex(u,v)最大值最小的构造图.
??考虑如何求Mex(u,v)的最大值.在同张图上,路径更长的边比路径更短的边Mex值要大.所以我们考虑树上的"链".
??如果只有一条链,任意构造即可.
??如果有>1条链子,由贪心思想,我们不要让0,1,2..在一条边上.但是发现放置0,1,不论怎么放都是在一条链上.那么放置0,1,2就不要让它们三在一条链子上.这样最大值最小是2.

Code

#include <iostream>
#include <algorithm>
#include <map>
using namespace std;
typedef pair<int,int> PII;
const int N = 100010;
vector<int> v[N];
PII p[N];
map<PII,int> mp;
int n,cnt;
int main()
{
	scanf("%d",&n);
	for(int i=1;i<n;i++)
	{
		int a,b; scanf("%d%d",&a,&b);
		p[++cnt] = {a,b};
		v[a].push_back(b),v[b].push_back(a);
	}
	int idx = 0;
	for(int i=1;i<=n;i++)
	  if(v[i].size()>2) idx = i;
	if(!idx)
	{
		for(int i=0;i<n-1;i++) printf("%d\n",i);
	}else{
		int j=0;
		for(int i=0;i<v[idx].size();i++)
		{
			int b = v[idx][i];
			PII x = {min(idx,b),max(idx,b)};
			mp[x] = j++;
			if(j>2) break;
		}
		for(int i=1;i<=cnt;i++)
		{
			if(p[i].first>p[i].second) swap(p[i].first,p[i].second);
			if(!mp.count(p[i])) mp[p[i]] = j++;
			printf("%d\n",mp[p[i]]);
		}
	}
	return 0;
}

Ehab and Path-etic MEXs CodeForces - 1325C

原文：https://www.cnblogs.com/newblg/p/14800546.html