求树的直径

两遍dfs过。
第一遍dfs先遍历到最远点（起点），第二遍dfs遍历到另一个最远点（终点），遍历个数就是直径。

代码如下：

#include
#include
#include
using namespace std;

int n,tot,t;
int head[400010],vis[400010],size[400010];
int ans,pos;

struct node{
	int to,nxt;
}e[400010];

void add(int u, int v){
	e[++tot].to = v;
	e[tot].nxt = head[u];
	head[u] = tot;
}

void dfs(int u){
	vis[u] = 1;
	size[u] = 1;
	int maxn = 0;
	for(int i = head[u]; i; i=e[i].nxt){
		int v = e[i].to;
		if(vis[v]) continue;
		dfs(v);
		size[u] += size[v];
		maxn = max(maxn,size[v]);
	}
	maxn = max(maxn,n-size[u]);
	if(maxn < ans || (maxn == ans && u < pos)){
		ans = maxn;
		pos = u;
	}
}

int main(){
	cin>>t;
	for(int k = 1; k <= t; k++){
		tot = 0;
		ans = pos = 0x7f7f7f;
		cin>>n;
		for(int i = 1; i < n; i++){
			int x,y;
			cin>>x>>y;
			add(x,y); add(y,x);	
		}
		dfs(1);
		cout< 
也可以树形动规。