传送门
题目描述
如题,给定一棵有根多叉树,请求出指定两个点直接最近的公共祖先。
输入
第一行包含三个正整数N、M、S,分别表示树的结点个数、询问的个数和树根结点的序号。
接下来N-1行每行包含两个正整数x、y,表示x结点和y结点之间有一条直接连接的边(数据保证可以构成树)。接下来M行每行包含两个正整数a、b,表示询问a结点和b结点的最近公共祖先。
输出
输出包含M行,每行包含一个正整数,依次为每一个询问的结果。
样例
- Input5 5 43 12 45 11 42 43 23 51 24 5
- Output44144
题解
- 用father[i][j]表示节点i向上走2^j的节点,father[i][0]自然就是i的父节点,
father[i][j]=father[father[i][j-1]][j-1]
。- 当查询a和b的最近公共祖先时,最暴力的方法就是先把两个节点深度统一,然后一起往上一步一步走,到相同为止。用father数组处理后,每次就可以一段一段地往上面走。
- 假设a的深度比b大,先将a移动到和b深度相同的位置,每次向上走
2^(log(depth[x]-depth[y])/log(2.0))
个,直到a,b深度相同为止。- 当两个深度相同后,从
i=log(depth[x])/log(2.0)
开始,只要father[x][i]和father[y][i]不同,就往上面跳,i递减,这样只要他们有公共祖先,就一定能跳到公共祖先的孩子位置。- 用递推的方法求lg数组,lg[i]表示
log(i)/log(2)+1
.- 链式向前星存图
Code
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 43 44 45 46 47 48 49 50 51 52 | #include |