Problem : Problem - C - Codeforces
I’m not unable to understand the problem. I need an explanation of the problem along with the some brief logic of solution. Can someone explain please? TIA
You have to assign numbers to the edges such that for all pair of vertices (u,v), when you traverse the path between them, then the MEX of all such paths is minimized .
If you draw any tree such that there is no vertex of degree three or more then there will be always a path for which MEX is n-1.So, in that case it actually doesn’t matter how you place the edges.
But, when you found a vertex with degree 3 or more, you should assign value 0,1 and 2 around it. Assign rest values arbitrary.
Implementation is easy:
/*author - Ashutosh Chitranshi*/
#include<bits/stdc++.h>
using namespace std;
#pragma GCC push_options
#pragma GCC optimize ("unroll-loops")
#define watch(x) cout << (#x) << " is " << (x) << "\n"
#define watch2(x,y) cout <<(#x)<<" is "<<(x)<<" and "<<(#y)<<" is "<<(y)<<"\n"
#define pow2(x) ((x)*(x))
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
#define ll long long
#define ld long double
#define eb emplace_back
#define pb push_back
#define pf push_front
#define mod 1000000007
#define clock (clock() * 1000.0 / CLOCKS_PER_SEC)
#define mp make_pair
#define ff first
#define ss second
#define null NULL
#define all(c) (c).begin(),(c).end()
#define nl "\n"
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector< vi > vvi;
typedef vector< vl > vvl;
typedef pair< int,int > ii;
typedef pair< ll,ll> pll;
typedef map< ll,ll> mll;
typedef map< int,int> mii;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
ll n;
cin >> n;
vector<pll> vect;
ll deg[n] = {0};
for(int i=0;i<n-1;i++)
{
ll u,v;
cin >> u >> v;
deg[u-1]++;
deg[v-1]++;
vect.eb(mp(u-1,v-1));
}
ll vertex = -1ll;
for(int i=0;i<n;i++)
{
if(deg[i]>=3)
{
vertex = i;
break;
}
}
if(vertex==-1ll)
{
for(int i=0;i<n-1;i++)
cout << i << nl;
exit(0);
}
ll val = 0ll;
ll val1 = 3ll;
for(int i=0;i<n-1;i++)
{
if((vect[i].ff == vertex || vect[i].ss == vertex) && val<3)
cout << val++ << nl;
else
cout << val1++ << nl;
}
return 0;
}
2 Likes
Dude you don’t need to #define max like that for multiple values…just write max({a,b,c}) and it works…for as many values as you want
3 Likes
Thanks. I don’t know about that. 
I assigned minimum numbers to leaf node containing edges and got AC.
I would like to know if it gets wrong on some testcase.
link to my solution