【LightOJ】1094 - Farthest Nodes in a Tree（树的直径）

#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
#define CLR(a,b) memset(a,b,sizeof(a))
#define INF 0x3f3f3f3f
#define MAX 40000
int n;
vector<int> mapp[MAX+5];
vector<int> dis[MAX+5];
int f[MAX+5];		//距离当前点的距离 
bool vis[MAX+5];
void init()
{
	for (int i = 0 ; i < n ; i++)
	{
		mapp[i].clear();
		dis[i].clear();
	}
}
int dfs(int x)
{
	int ans;		//最远点 
	int maxx = 0;		//最大距离 
	queue<int> q;		//存放根 
	CLR(vis,false);
	CLR(f,0);
	f[x] = 0;
	q.push(x);
	while (!q.empty())
	{
		int st = q.front();
		q.pop();
		vis[st] = true;
		for (int i = 0 ; i < mapp[st].size() ; i++)
		{
			if (!vis[mapp[st][i]])		//该点没有用过 
			{
				q.push(mapp[st][i]);
				f[mapp[st][i]] = f[st] + dis[st][i];
				if (f[mapp[st][i]] > maxx)
				{
					maxx = f[mapp[st][i]];
					ans = mapp[st][i];		//记录节点 
				}
			}
		}
	}
	return ans;
}
int main()
{
	int u;
	int Case = 1;
	scanf ("%d",&u);
	while (u--)
	{
		scanf ("%d",&n);
		init();
		for (int i = 1 ; i < n ; i++)
		{
			int t1,t2,t3;
			scanf ("%d %d %d",&t1,&t2,&t3);
			mapp[t1].push_back(t2);
			dis[t1].push_back(t3);
			mapp[t2].push_back(t1);		//求树的直径一定要双向存图 
			dis[t2].push_back(t3);
		}
		int st = dfs(0);		//任意从一点开始bfs
		int ans = dfs(st);
		printf ("Case %d: %d\n",Case++,f[ans]);
	}
	return 0;
}