首页 > 试题广场 >

两棵树的问题

[编程题]两棵树的问题
  • 热度指数：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
算法知识视频讲解
添加回答
C++
martin0621头像 martin0621
通过的同学们，你们数组越界了没发现么？本地IDE随便跑个小规模例子，内存污染把树上倍增法搞炸啦，放到牛客这里编译就没问题，这内存管理真是厉害。把越界改过来之后通过23/25，怀疑剩下两组数据答案有错已经报错。
发表于 2021-08-28 16:20:27 回复(0)
zlc1114头像 zlc1114
做法：
可以简单的使用树分治，枚举第一棵树的LCA
对第二颗树的LCA，用set维护dfs序建立虚树，lower_bound和upper_bound为对应lca最大的点，正确性很明显成立
复杂度两个log，其中有个log比较小
不用树分治也可以直接dfs带个set的merge，复杂度一样是两个log，不知道有没有一个log的做法

发表于 2021-03-22 16:20:21 回复(0)
没事儿干头像 没事儿干
这个题目没问题吗？有人放出标准答案没，题例测过了，运行超时且通过率0，感觉不太对呢
编辑于 2020-10-28 10:39:04 回复(0)
牛客511428626号头像 牛客511428626号
有两棵大小为n且以1为根的树,令根的深度为0,所以1的深度为0？
编辑于 2020-07-29 21:12:53 回复(1)
提交观点

问题信息

树
难度：
4条回答 2113浏览

热门推荐

通过挑战的用户

查看代码

相关试题

两棵树的问题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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