3022: 【普及/提高-】【P3884】二叉树问题
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：2
解决：2
题目描述
如下图所示的一棵二叉树的深度、宽度及结点间距离分别为：
- 深度：
- 宽度：
- 结点 8 和 6 之间的距离：
- 结点 7 和 6 之间的距离：
其中宽度表示二叉树上同一层最多的结点个数，节点 之间的距离表示从 到 的最短有向路径上向根节点的边数的两倍加上向叶节点的边数。
给定一颗以 1 号结点为根的二叉树，请求出其深度、宽度和两个指定节点 之间的距离。
输入
第一行是一个整数，表示树的结点个数 。
接下来 行，每行两个整数 ，表示树上存在一条连接 的边。
最后一行有两个整数 ，表示求 之间的距离。
接下来 行，每行两个整数 ，表示树上存在一条连接 的边。
最后一行有两个整数 ，表示求 之间的距离。
输出
输入三行，每行一个整数，依次表示二叉树的深度、宽度和 之间的距离。
样例输入 复制
10
1 2
1 3
2 4
2 5
3 6
3 7
5 8
5 9
6 10
8 6样例输出 复制
4
4
8提示
对于全部的测试点，保证 ，且给出的是一棵树。
#include<bits/stdc++.h>
using namespace std;
struct node {
int left,right,father,depth;
}ns[105];
struct node2{
int pos,step;
};
int deep,wide,width[105],visited[105];
void dfs(int pos) {
if(visited[pos]) return;
visited[pos] = 1;
int left=ns[pos].left,right=ns[pos].right,depth=ns[pos].depth;
deep=max(deep,depth);
width[depth]++;
if(left) {
ns[left].depth=depth+1;
dfs(left);
}
if(right) {
ns[right].depth=depth+1;
dfs(right);
}
}
int main(){
int n,u,v,x,y;
cin>>n;
for(int i=1;i<n;i++) {
cin>>u>>v;
if(!ns[ u ].left) ns[ u ].left=v;
else ns[ u ].right=v;
ns[v].father=u;
}
cin>>x>>y;
ns[1].depth=1;
dfs(1);
for(int i=1;i<=n;i++) wide=max(wide,width[i]);
cout<<deep<<endl<<wide<<endl;
memset(visited,0,sizeof(visited));
node2 tn={x,0};
visited[x]=1;
queue<node2> q;
q.push(tn);
while(!q.empty()) {
tn=q.front();
q.pop();
if(tn.pos==y) {
cout<<tn.step;
break;
}
int left=ns[tn.pos].left,right=ns[tn.pos].right,father=ns[tn.pos].father,step=tn.step;
if(left && !visited[left]) {
visited[left]=1;
q.push({left,step+1});
}
if(right && !visited[right]) {
visited[right]=1;
q.push({right,step+1});
}
if(father && !visited[father]) {
visited[father]=1;
q.push({father,step+2});
}
}
return 0;
}