【题解】树的直径

题目描述
给定一棵拥有 n 个结点的树，1 号点为根，请找出这棵树的直径。所谓直径就是树上最远的两点的距离。

输入格式
第一行：单个整数表示 n；
第二行：n−1 个整数表示 p_2到 p_n，p_i表示 i 号点父亲的编号，保证有 1≤pi<i。

输出格式
单个整数：表示树的直径。

数据范围
对于 30%30% 的数据，n≤20；
对于 60%60% 的数据， n≤5000；
对于 100%100% 的数据， 1≤n≤200,000。
样例数据
输入:
4
1 1 1
输出:
2
输入:
4
1 2 3
输出:
3
【题解】
暴力：
使用一次bfs 或者 dfs 求出所有点和v 的距离，然后再用n次搜索，找到所有点的距离。(部分数据超时）
使用结论
任选一个点v，找距离v最远的一个点u，再找一个点u最远的点w，则u-w 是最远距离。
可以使用搜索完成题目。（广搜，若用深搜，当点是一路悬挂下来的话，栈空间开销过大）

#include<bits/stdc++.h>
#include <iostream>　　　　 // cin  cout的头文件  基本输入流
#include <iomanip>　　　//cout输出时，保留小数fixed、setprecision的头文件 参数化输入／输出
#include <cstdio>　　　　//scanf、printf的头文件  定义输入／输出函数
#include <cmath>　　　　　//sqrt()求平方根、定义数学函数
#include <algorithm>　　　 //STL通用算法
#include <cstring>
#include <string>
using namespace std;
const int N=2e5+10;
vector<int> e[N];//e[i]存储 与i相邻的节点 
int last,dis;//记录 哪个距离s最远，最远距离是多少
bool vis[N];//是否访问过 
struct node{
	int f;//当前点 
	int l;//距离 
};
queue<node>q;
void bfs(int s){
	memset(vis,0,sizeof(vis));
	vis[s]=1;
	node n_p;
	n_p.f=s;
	n_p.l=0; 
	q.push(n_p);
	while(!q.empty()){
		node p=q.front();
		q.pop();
		last=p.f;
		dis=p.l;
		for(int i=0;i<e[p.f].size();i++){
			int x=e[p.f][i];
			if(vis[x])
			continue;
			node nxp;
			nxp.f=x;
			nxp.l=p.l+1;
			q.push(nxp);
			vis[x]=1;
		}
	}
} 
int main(){
	int n;
	cin>>n;
	for(int i=2;i<=n;i++){
		int f;
		cin>>f;
		e[f].push_back(i);
		e[i].push_back(f);
	}
	//
	bfs(1);
	bfs(last);
	cout<<dis;
	return 0;
}