两棵树的问题

[编程题]两棵树的问题

热度指数：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]

输出

备注:

输入时给出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

算法知识视频讲解