洛谷——P3884 [JLOI2009] 二叉树问题（最近公共祖先，LCA）c++

---

一、题目

[JLOI2009] 二叉树问题

题目描述

如下图所示的一棵二叉树的深度、宽度及结点间距离分别为：

• 深度：$4$
• 宽度：$4$
• 结点 8 和 6 之间的距离：$8$
• 结点 7 和 6 之间的距离：$3$

其中宽度表示二叉树上同一层最多的结点个数，节点 $u,v$ 之间的距离表示从 $u$ 到 $v$ 的最短有向路径上向根节点的边数的两倍加上向叶节点的边数。

给定一颗以 1 号结点为根的二叉树，请求出其深度、宽度和两个指定节点 $x,y$ 之间的距离。

输入格式

第一行是一个整数，表示树的结点个数 $n$。
接下来 $n?1$ 行，每行两个整数 $u,v$，表示树上存在一条连接 $u,v$ 的边。
最后一行有两个整数 $x,y$，表示求 $x,y$ 之间的距离。

输出格式

输出三行，每行一个整数，依次表示二叉树的深度、宽度和 $x,y$ 之间的距离。

样例 #1

样例输入 #1

10                                
1 2                            
1 3                            
2 4
2 5
3 6
3 7
5 8
5 9
6 10
8 6

样例输出 #1

4
4
8

提示

对于全部的测试点，保证 $1\le u,v,x,y\le n\le 100$，且给出的是一棵树。

基本思路：

• (1) 求出二叉树的深度，只需要dfs一遍求得每个节点的深度，然后取最大值即为二叉树的深度
• (2)求二叉树宽度，某个深度节点数最多的即为宽度
• (3) 求两点间的距离（最短有向路径上向根节点的边数的两倍加上向叶节点的边数），因为时有方向的，可以求出两点的LCA（最近公共祖先）,然后答案所求距离就是向根节点到LCA的距离的2倍加上向叶节点到LCA的距离。

#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define endl "\n"
#define int long long
#define fi first
#define se second
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define gcd __gcd
#define repn(i,a,n) for(int i = a; i <= n; i++)
#define rep(i,a,n) for(int i = a; i < n; i++)
typedef pair<int,int> PII; 
const int N = 110;
vector<int> edge[N];
int n,dist[N],fa[N];//分别记录dist:节点深度、以及fa：每个节点的父亲是谁 
int pre[N],x,y,bx,by;  //pre记录i从哪里来的
int depth,width,ans;// 依次表示二叉树的深度、宽度和 x,y 之间的距离

inline void dfs(int x){
	for(auto y:edge[x]){
		if(pre[x]!=y){
			pre[y]=x;//需要记录一下y来自那个节点，不然会死循环
			dist[y]=dist[x]+1;//y的深度等于x的深度加1
			fa[y]=x;//y的父亲节点是x
			dfs(y);
		}
	}

}

void solve(){
	cin>>n;
	rep(i,1,n){
		int u,v;
		cin>>u>>v;
		edge[u].pb(v);
		edge[v].pb(u);
	}  
	cin>>x>>y;
	bx=x,by=y;
	pre[1]=-1;
	dist[1]=1;//根节点的深度为1 
	dfs(1);//求出每个节点的深度 
	/*
	//每个节点的深度 
	for(int i=1;i<=n;i++)
	  cout<<i<<": "<<dist[i]<<endl;
	cout<<endl;
	//每个节点的父亲节点是谁 
	for(int i=1;i<=n;i++)
	  cout<<i<<": "<<dist[i]<<endl;
	*/
	//求出深度,即dist最大值 
	repn(i,1,n)
	  depth=max(depth,dist[i]);
	//求出宽度，即某深度节点数最多 
	repn(i,1,depth){
		int sum=0;
		repn(j,1,n)
		  if(dist[j]==i) sum++;
		width=max(width,sum);
	} 
	cout<<depth<<endl<<width<<endl;
	
	// 求x,y 之间的距离
	//首先找到x、y的最近公共祖先
	int step;
	if(dist[x]>dist[y]){
	 	step=dist[x]-dist[y];//深度较大的跳多少步可以达到同一深度
		repn(i,1,step)
	 		x=fa[x]; 
	}else{
		step=dist[y]-dist[x];//深度较大的跳多少步可以达到同一深度
		repn(i,1,step)
	 		y=fa[y]; 
	}    
	while(x!=y){//当x==y时，找到了x,y的最近公共祖先 
		x=fa[x],y=fa[y]; 
	} 
	//此时x、y均为起始的bx、by的LCA
	ans=(dist[bx]-dist[x])*2+(dist[by]-dist[y]);
	cout<<ans<<endl;
}

signed main(){
	IOS;
	int T=1;
	//cin>>T;
	while(T--){
		solve();
	}
	return 0;
}