Razvan's wiki

*2005-2009 Liceul International de informatica Bucuresti *2009-prezent Universitatea Politehnica Bucuresti

*sunt smecher ce sa mai….

Mircea Ghideu

Mitra M. George-Daniel

#include<stdio.h>
#include<assert.h>
#include<vector>
#include<algorithm>
#define pb push_back
#define mkp make_pair

using namespace std;
const int maxn = 340;

vector<short> VECT[maxn];
vector<pair<short,short> > ANS,AUX,VEC;
short N,MOVE,COST;
short VER[maxn];
short NRT,TATA[maxn];
short D[maxn][maxn],M[maxn][maxn];

bool cmpf(pair<short,short> p1,pair<short,short> p2)
{
	short n1 = p1.first;
	short n2 = p2.first;
	short i1 = p1.second;
	short i2 = p2.second;
	for(;i1 <= N && i2 <= N;++i1,++i2)
	{
		if (D[n1][i1] != D[n2][i2]) return D[n1][i1] < D[n2][i2];
                if (D[n1][i1] == 0) return false;
        }
	return false;
}

bool ver(vector<pair<short,short> > v1,short timp)
{
	sort(v1.begin(),v1.end(),cmpf);
        MOVE = 0;
	for(int i = v1.size() - 1;v1.size();)
	{
                if (timp < 0) return false;
		if (timp < D[v1[i].first][v1[i].second]) return false;
		if (timp > D[v1[i].first][v1[i].second])
		{
			if (!MOVE) MOVE = v1[i].first;	
			v1.pop_back();--i;
			timp--;
			continue;
		}
		if (timp == D[v1[i].first][v1[i].second])
		{
			if(!MOVE) MOVE = M[v1[i].first][v1[i].second];
			v1[i].second++;
			timp--;
                        while(i != 0 && cmpf(v1[i],v1[i - 1])) swap(v1[i],v1[i - 1]);
			//sort(v1.begin(),v1.end(),cmpf);
			continue;
		}
	}
        if (timp < 0) return false;
	return true;	
}

void solve(vector<pair<short,short> > &v)
{
        if (v.size() == 0) {COST = 0;return;}
	short x = 0,p;
        for(p = 1;p < N; p <<= 1);
	for(;p;p >>= 1)
		if (!ver(v,x + p))
		{
			x += p;	
		}
	x++;
	ver(v,x);
	COST = x;
}

void dfs(int nod)
{
	if (VER[nod]) return ;
	VER[nod] = 1;
	for(int i = 0;i < (int)VECT[nod].size(); ++i)
	{
                if (!VER[VECT[nod][i]]) TATA[VECT[nod][i]] = nod;
		dfs(VECT[nod][i]);	
	}
	VEC.clear();
	for(int i = 0;i < (int)VECT[nod].size(); ++i)
	{
		if (VER[VECT[nod][i]] == 2)VEC.pb(mkp(VECT[nod][i],0));	
	}
	for(int i = 0;i < N && VEC.size() > 0;++i)
	{
		solve(VEC);
		D[nod][i] = COST;
		M[nod][i] = MOVE;
		for(int i = 0;i < (int)VEC.size(); ++i)
		{
			if (VEC[i].first == MOVE)
			{
				VEC[i] = VEC[VEC.size() - 1];
				VEC.pop_back();
			}
			if (M[VEC[i].first][VEC[i].second] == MOVE) VEC[i].second += 1;	
		}
	}
	VER[nod] = 2;
}

int main()
{
	freopen("optic.in","r",stdin);
	freopen("optic.out","w",stdout);
	scanf("%d\n",&N);
	for(int i = 1;i < N; ++i)
	{
		short x,y;
		scanf("%hd %hd\n",&x,&y);
                assert(x != 0 && y != 0);
		VECT[x].pb(y);
		VECT[y].pb(x);
	}
	dfs(1);

        memset(VER,0,sizeof(VER));
	printf("%d\n",D[1][0]);
        ANS.pb(mkp(1,0));
        VER[1] = 1;
        for(int i = 1;i <= D[1][0]; ++i)
        {

                AUX.clear();
                for(int j = 0;j < ANS.size(); ++j)
                {
                        if (VER[M[ANS[j].first][ANS[j].second]] == 0 && M[ANS[j].first][ANS[j].second])
                        {
                                AUX.pb(mkp(ANS[j].first,M[ANS[j].first][ANS[j].second]));
                                VER[M[ANS[j].first][ANS[j].second]] = 1;
                                ANS[j].second++;
                        }
                }
                printf("%d\n",AUX.size());
                for(int j = 0;j < AUX.size(); ++j)
                {
                        printf("%d %d\n",AUX[j].first,AUX[j].second);
                        NRT = 0;
                        int nod = AUX[j].second;
                        for(NRT;VER[M[nod][NRT]];++NRT);
                        ANS.pb(mkp(AUX[j].second,NRT));
                }
        }

	return 0;
}