题解 P3884 【[JLOI2009]二叉树问题】

我一定要发这篇题解

其因有二:我思路清奇,题解中没人用这种方法,自我感觉良好

讲之前先陈述三个事实:

题解里的lca我真的不会,看来我还是太弱了

这道题对于普及/提高-来说太简单了

标签里的”最近公共祖先,LCA树上距离深度优先搜索,DFS”是假的

可以开始了…………


解题思路

经过剖析样例,我微微思索手动模拟后发现
要找最近的公共祖先,一次次地向上找就好了嘛,其实这有点并查集地意思

寻找时可分为两种情况
1.两点在不同子树中,有公共祖先
2.其中一个点是另一个的祖先

那么代码可以这么写

谁在下面谁就向上走,u向上时用depp1记录,v向上时depp2记录

1
2
3

if(tr[u].deep>tr[v].deep){depp1++;u=tr[u].fa;}
if(tr[v].deep>tr[u].deep){depp2++;v=tr[v].fa;}

两点在同一层但祖先不同时(在不同子树),同时向上走

1
2
if(tr[u].deep==tr[v].deep&&tr[u].fa!=tr[v].fa)
{depp1++;u=tr[u].fa;depp2++;v=tr[v].fa;}

发现有一点是另一点祖先时,
u是v的祖先输出depp2+1(u是v祖先,u在v之上,只能是v向上走)
v是u祖先时输出(depp1+1)*2(同理只有v能向上)

注意!!这种情况一定要先判断!!

1
2
if(tr[u].fa==v){cout<<(depp1+1)*2;return 0;}
if(tr[v].fa==u){cout<<depp2+1;return 0;}

剩下深度宽度什么的都很好办,
宽度:我这里开了一个数组dep来记录第i层有多少节点;最后找一遍输出最大值就行了;
深度:建树时直接记录;

我这种方法其实是简化了题目

我不管你是二叉树,还是二十万叉树(>_>…)

由于这个算法只向上进行,根本不用知道谁是谁的子树,只需要记住宽度与父节点就好了

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include<iostream>//P3884
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
using namespace std;
struct node
{int fa,deep;}tr[200];
int n,ans=1,sum=0;//ans是深度sum是宽度
int dep[200];
int main()
{
int i,u,v;
cin>>n;tr[1].deep=1;dep[1]=1;
for(i=1;i<n;i++)
{
cin>>u>>v;
tr[v].fa=u;//v的父亲是u
tr[v].deep=tr[u].deep+1;//v的深度是u的深度+1
if(tr[v].deep>ans)ans=tr[v].deep;
//最大深度
dep[tr[v].deep]++;//记录宽度,即每层结点数
}
cin>>u>>v;
for(i=1;i<=ans;i++)
if(dep[i]>sum)sum=dep[i];
cout<<ans<<endl<<sum<<endl;
if(u==v){cout<<0;return 0;}
int depp1=0,depp2=0;
while(tr[u].fa!=tr[v].fa)//不破楼兰终不还
{
if(tr[u].fa==v){cout<<(depp1+1)*2;return 0;}
if(tr[v].fa==u){cout<<depp2+1;return 0;}
if(tr[u].deep>tr[v].deep){depp1++;u=tr[u].fa;}
if(tr[v].deep>tr[u].deep){depp2++;v=tr[v].fa;}
if(tr[u].deep==tr[v].deep&&tr[u].fa!=tr[v].fa)
{depp1++;u=tr[u].fa;depp2++;v=tr[v].fa;}
}
cout<<(depp1+1)*2+depp2+1;
//+1是因为离父节点还有一层,你只是找到了,并没有到达
return 0;
}


总结
感觉这个自创算法还不错 ,循环最多n-1次;那么时间复杂度就是O(n-1)?(>_>……)

解题不易,顺手留赞,感激不尽~(>_<*)