内存限制: 256 Mb时间限制: 1000 ms
题目描述
给定一棵拥有 n 个结点的树，1 号点为根，请找出这棵树的直径。所谓直径就是树上最远的两点的距离。
输入格式
第一行：单个整数表示 n；
第二行：n−1 个整数表示 p2 到 pn ，pi 表示 i 号点父亲的编号，保证有 1≤pi<i。
输出格式
单个整数：表示树的直径。
数据范围
对于 30% 的数据， n≤20；
对于 60% 的数据， n≤5000；
对于 100% 的数据， 1≤n≤200,000。
样例数据
输入:
4
1 1 1
输出:
2
输入:
4
1 2 3
输出:
3
题目解析：
模板题，求树的直径是一个很经典的问题。
暴力求解方案：用bfs 或者 dfs 求出所有点和v点的距离，O(n)次搜索，就能够找到所有两点之间的距离。n是2*10^5,n*n的时间复杂度会超时。
因此，我们需要使用一些数学的结论：
任选一点v，找到离v点最远的一个点u,再找到离u最远的点w,则u--w是一条直径。
有了这个结论后，做两次搜索即可解决本题。
但要注意：如果所有的点形成一条线悬挂下来，则对于深度优先搜索，容易产生栈溢出。
所以，最好使用广度优先搜索(全局变量队列)。
1. #include <bits/stdc++.h> 2. using namespace std; 3. const int N=2e5+10; 4. vector<int> e[N];//e[i]里存储的是和i相邻的节点 5. int last,dis;//用来记录那个点距离s最远 最远的距离为多少 6. typedef pair<int,int>pii;//字典结构体 7. bool vis[N];//标记该点是否被访问过 8. queue<pii> q;//队列 9. void bfs(int s){ 10. memset(vis,0,sizeof(vis));//初始化vis 11. vis[0]=1; 12. q.push(pii{s,0});//s为出发点 入队 13. while(!q.empty()){ 14. pii pr=q.front();//保存对头 15. q.pop();//出队 16. last=pr.first;//更新最远节点 17. dis=pr.second;//更新最大距离 18. for(auto x:e[pr.first]){//查找下一个节点 19. if(vis[x]) continue; //是否已经过 20. q.push(pii{x,pr.second+1});//入队新节点 21. vis[x]=1;//更新标记 22. } 23. } 24. } 25. int main() 26. { 27. int n,f; 28. cin>>n; 29. for(int i=2;i<=n;i++){ 30. cin>>f; 31. e[f].push_back(i); 32. e[i].push_back(f); 33. } 34. bfs(1);//广搜根节点 找到离根节点最远的点last 35. bfs(last);//广搜last 计算离last最远距离dis 36. cout<<dis; 37. return 0; 38. }
