首页 > 试题广场 >

两棵树的问题

[编程题]两棵树的问题
  • 热度指数：237 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
有两棵大小为n且以1为根的树，设为树1和树2，令根的深度为0，在树1上编号为x的点，在树2中编号为a[x]。
定义点对(x,y)的价值为树1中x和y的最近公共祖先的深度+树2中a[x]和a[y]的最近公共祖先的深度。
输出所有点对的价值的最大值。
示例1

输入

3,[0,2,1,3],[0,0,1,1],[0,0,1,2]

输出

1

备注:
输入时给出n和三个数组a,b,c。
a数组下标从0到n，意义如题,保证a[0]=0,a[1]~a[n]的数互不相同且1~n各只出现一次。
b数组下标从0到n，为描述树1的数组，b[x]表示树1上x的父亲节点的编号，其中b[0]=b[1]=0.
c数组下标从0到n，为描述树2的数组，c[x]表示树2上x的父亲节点的编号，其中c[0]=c[1]=0.
输出一个整数，表示最大的价值。
n<=100000
算法知识视频讲解
开通博客
头像 辣条咸鱼王
发表于 2020-07-24 16:33:00
这题我超时了，思路应该 是对滴，本地用例通过了。 class Solution { public: /** * * @param n int整型 * @param a int整型一维数组 * @param aLen int a数组长度 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 摸鱼学大师
发表于 2021-09-03 15:52:42
思路： 题目的主要信息： 有两个结点数都为n，根都是1的树，设根的深度为0 定义点对(x,y)的价值为树1中x和y的最近公共祖先的深度+树2中a[x]和a[y]的最近公共祖先的深度 输出所有点对的最大值价值数组b与数组c分别记录树1与树2的各个节点的父节点 方法一：暴力解法（超时）具体做法：我们 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

树
难度：
4条回答 2119浏览

热门推荐

通过挑战的用户

查看代码

相关试题

两棵树的问题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号