一天牛牛整理旧物时发现了一张家谱(家谱可以看做一棵树)。由于年代久远,家谱已经模糊了,现在只能看见人与人之间有直接关系,但是看不出来直接关系是什么了(就是说现在还能直接看出u与v之间有父子关系,但是看不出来是u是v的父亲还是v是u的父亲了)。牛牛还不知道他们家族的最大祖先(根节点)是谁,这样显然就不知道家谱中任意两个人是什么关系了,但是牛牛的爷爷告诉了牛牛家每个人都有多少个孩子(显然叶子节点的孩子数为0),这样就可以推出人与人之间的关系了。家谱中一共有n个人,编号为1~n。牛牛现在有q次询问,对于每个询问,有两个数u和v。对于每组询问输出一行表示他们之间关系。-笔试面试资料

这是qklbishe.com第7251 篇笔试面试资料
提供答案分析,通过本文《 一天牛牛整理旧物时发现了一张家谱(家谱可以看做一棵树)。由于年代久远,家谱已经模糊了,现在只能看见人与人之间有直接关系,但是看不出来直接关系是什么了(就是说现在还能直接看出u与v之间有父子关系,但是看不出来是u是v的父亲还是v是u的父亲了)。牛牛还不知道他们家族的最大祖先(根节点)是谁,这样显然就不知道家谱中任意两个人是什么关系了,但是牛牛的爷爷告诉了牛牛家每个人都有多少个孩子(显然叶子节点的孩子数为0),这样就可以推出人与人之间的关系了。家谱中一共有n个人,编号为1~n。牛牛现在有q次询问,对于每个询问,有两个数u和v。对于每组询问输出一行表示他们之间关系。-笔试面试资料》可以理解其中的代码原理,这是一篇很好的求职学习资料
本站提供程序员计算机面试经验学习,笔试经验,包括字节跳动/头条,腾讯,阿里,美团,滴滴出行,网易,百度,京东,小米,华为,微软等互联网大厂真题学习背诵。

答案:
 一天牛牛整理旧物时发现了一张家谱(家谱可以看做一棵树)。由于年代久远,家谱已经模糊了,现在只能看见人与人之间有直接关系,但是看不出来直接关系是什么了(就是说现在还能直接看出u与v之间有父子关系,但是看不出来是u是v的父亲还是v是u的父亲了)。牛牛还不知道他们家族的最大祖先(根节点)是谁,这样显然就不知道家谱中任意两个人是什么关系了,但是牛牛的爷爷告诉了牛牛家每个人都有多少个孩子(显然叶子节点的孩子数为0),这样就可以推出人与人之间的关系了。家谱中一共有n个人,编号为1~n。牛牛现在有q次询问,对于每个询问,有两个数u和v。对于每组询问输出一行表示他们之间关系。

 一天牛牛整理旧物时发现了一张家谱(家谱可以看做一棵树)。由于年代久远,家谱已经模糊了,现在只能看见人与人之间有直接关系,但是看不出来直接关系是什么了(就是说现在还能直接看出u与v之间有父子关系,但是看不出来是u是v的父亲还是v是u的父亲了)。牛牛还不知道他们家族的最大祖先(根节点)是谁,这样显然就不知道家谱中任意两个人是什么关系了,但是牛牛的爷爷告诉了牛牛家每个人都有多少个孩子(显然叶子节点的孩子数为0),这样就可以推出人与人之间的关系了。家谱中一共有n个人,编号为1~n。牛牛现在有q次询问,对于每个询问,有两个数u和v。对于每组询问输出一行表示他们之间关系。 区块链毕设学生138243653号
import sys    sys.setrecursionlimit(100000) import math def findTree(root,con):     if con[root]:         for i in con[root]:             fatherNum[i] = fatherNum[root]+1             l=int(math.log2(fatherNum[i]))             fathers[i]=[root]             for j in range(l):                 fathers[i].append(fathers[fathers[i][j]][j])             con[i].remove(root)             findTree(i,con)        def LCA(u,v,fathers):     if fatherNum[u]<fatherNum[v]:         u,v=v,u     #把u和v调整到同一高度     while fatherNum[u]>fatherNum[v]:         u = fathers[u][int(math.log2(fatherNum[u]-fatherNum[v]))]     if u==v:         return u     for k in range(int(math.log2(fatherNum[u])),-1,-1):         #往上跳到一半的位置         if fathers[u][k]!=fathers[v][k]:             u = fathers[u][k]             v = fathers[v][k]     return fathers[u][0]  n = int(input()) con ={} lineNum = [0 for i in range(n+1)] for i in range(n-1):     u,v = map(int,input().split())     if u not in con:         con[u]=[]     if v not in con:         con[v]=[]     con[u].append(v)     con[v].append(u)     lineNum[u]+=1     lineNum[v]+=1 num = list(map(int,input().split())) fathers = [[] for i in range(n+1)] #fathers[i][j]中储存i的第2^j个祖先 fatherNum = [0 for i in range(n+1)] #fatherNum[i]记录i的祖先个数 for i in range(n):     if num[i] == lineNum[i+1]:          #如果子节点数和连边数相同,说明没有父节点,是根节点         findTree(i+1,con)         break  q = int(input()) for j in range(q):     u,v = map(int,input().split())     w = LCA(u,v,fathers)     if w==u:         print('ZZZZ')     elif w==v:         print('SSSS')     else:         print(w)

这种答案一直超时,不知道是否有更高效的从所有连边和子节点数还原出整棵树的算法。查找最近共同祖先的算法感觉已经是log(N)的复杂度了,不会更好了。如果有人做出来,烦请评论回复一下。谢谢

今天 01:01:50 回复(0)

文章部分来自互联网,侵权联系删除
www.qklbishe.com

区块链毕设网(www.qklbishe.com)全网最靠谱的原创区块链毕设代做网站
部分资料来自网络,侵权联系删除!
资源收费仅为搬运整理打赏费用,用户自愿支付 !
qklbishe.com区块链毕设代做网专注|以太坊fabric-计算机|java|毕业设计|代做平台 »  一天牛牛整理旧物时发现了一张家谱(家谱可以看做一棵树)。由于年代久远,家谱已经模糊了,现在只能看见人与人之间有直接关系,但是看不出来直接关系是什么了(就是说现在还能直接看出u与v之间有父子关系,但是看不出来是u是v的父亲还是v是u的父亲了)。牛牛还不知道他们家族的最大祖先(根节点)是谁,这样显然就不知道家谱中任意两个人是什么关系了,但是牛牛的爷爷告诉了牛牛家每个人都有多少个孩子(显然叶子节点的孩子数为0),这样就可以推出人与人之间的关系了。家谱中一共有n个人,编号为1~n。牛牛现在有q次询问,对于每个询问,有两个数u和v。对于每组询问输出一行表示他们之间关系。-笔试面试资料

提供最优质的资源集合

立即查看 了解详情