GCPC11J.cpp

#include <iostream>
using namespace std;

const int MAX = 100005;

typedef struct Node
{
	int id;
	Node *next;
}Node;

class List
{
public: 
	Node *begin;
public:
	List()
	{
		begin = 0;
	}

	void Add(int id)
	{
		Node *tmp = new Node;
		tmp->id	  = id;
		tmp->next = begin;
		begin = tmp;
	}

	int GetLength()
	{
		int cnt = 0;
		Node *p = begin;
		while (p!=0) 
		{
			cnt++;
			p = p->next;
		}
		return cnt;
	}
};

int N, Answer, IdMax;
List MyList[MAX];
int  Mark[MAX];

int queue[MAX];
int fr, re, leng;

void EnQueue(int id)
{
	queue[re] = id;
	re = (re + 1) % MAX;
	leng++;
}

int DeQueue()
{
	int p = queue[fr];
	fr = (fr + 1) % MAX;
	leng--;
	return p;
}

void BFS(int u)
{
	for(int i = 0; i < N; i++)
		Mark[i] = 0;
	fr = re = leng = 0;

	EnQueue(u);
	Mark[u] = 1;
	
	while(leng > 0)
	{
		int v = DeQueue();
		Node *p = MyList[v].begin;

		while(p != 0)
		{
			int k = p->id;
			if(!Mark[k])
			{
				Mark[k] = Mark[v] + 1;
				if(Mark[k] > Answer)
				{
					IdMax = k;
					Answer = Mark[k];
				}
				EnQueue(k);
			}
			p = p->next;
		}
	}
}

int main()
{
	ios::sync_with_stdio(false);
//	freopen("input.txt","r",stdin);

	int T;
	cin >> T;

	for(int tc = 0; tc < T; tc++)
	{
		IdMax = Answer = 0;
		cin >> N;
		for(int i = 0; i < N; i++)
			MyList[i].begin = 0;

		int a,b;
		for(int i = 0; i < N-1; i++)
		{
			cin >> a >> b;
			MyList[a].Add(b);
			MyList[b].Add(a);
		}

		BFS(1);
		BFS(IdMax);
		Answer--;

		if(Answer%2==0) Answer /= 2;
		else Answer = Answer / 2 + 1;

		cout << Answer << endl;
	}
	return 0;
}