Farthest Nodes in a Tree

Given a tree (a connected graph with no cycles), you have to find the farthest nodes in the tree. The edges of the tree are weighted and undirected. That means you have to find two nodes in the tree whose distance is maximum amongst all nodes.

Input
starts with an integer T (≤ 10), denoting the number of test cases. Each case starts with an integer n (2 ≤ n ≤ 30000) denoting the total number of nodes in the tree. The nodes are numbered from 0 to n-1. Each of the next n-1 lines will contain three integers u v w (0 ≤ u, v < n, u ≠ v, 1 ≤ w ≤ 10000) denoting that node u and v are connected by an edge whose weight is w. You can assume that the input will form a valid tree.

Output

For each case, print the case number and the maximum distance.

Sample Input

    2
    4
    0 1 20
    1 2 30
    2 3 50
    5
    0 2 20
    2 1 10
    0 3 29
    0 4 50

Sample Output

    Case 1: 100
    Case 2: 80

这个题刚开始一直不理解，可能是对树的的直径比较陌生吧，可后来看看了看学长给我板子。我去咋这么简单emmm，我真是个智障呀。只要从任意一个节点出发然后找到距离他最远的节点，然后再让这个最远的出发去找距离这个最远的，这两个节点的距离就是树的直径！
这就是一个简单的板子题

#include<iostream>
#include<cstring>
#include<queue>
#include<vector>
using namespace std;
typedef pair<int,int> pa;

bool flag[100100];
int step[100100];
vector<pa>v[100100];
int a,b,c,sum;
int t,n;

int dfs(int x)
{
    sum=0;
	memset(flag,0,sizeof flag);
	memset(step,0,sizeof step);
	queue<int>q;
	q.push(x);
	flag[x]=1;
	int yy=0;
	while(!q.empty() )
	{
		int xx=q.front() ;
		q.pop() ;
		if(step[xx]>sum)
		{
			sum=step[xx];
			yy=xx;
		}
		pa p;
		for(int i=0;i<v[xx].size() ;i++)
		{
			p=v[xx][i];
			int y=p.first ;
			if(!flag[y])
			{
				flag[y]=1;
				step[y]=step[xx]+p.second;
				q.push(y);
			}
		}
	}
	return yy;
}
int main()
{
	ios::sync_with_stdio(false);
	cin>>t;
	
		for(int i=1;i<=t;i++)
		{
			cin>>n;
			for(int k=0;k<n;k++) 
			    v[k].clear() ;
			for(int j=1;j<n;j++)
			{
				cin>>a>>b>>c;
				v[a].push_back(make_pair(b,c));//双向存储便于查找
			 	v[b].push_back(make_pair(a,c));	 
			}
			dfs(dfs(0));
			cout<<"Case "<<i<<": "<<sum<<endl;
		}
	
	return 0;
}