今天是连续打卡的第45天。

今天开始图论II的第一部分：LCA（最近公共祖先）

某些题目只有一组数据，这样不能判断程序是否正确，希望老师如果有时间再加3-5组数据。

第一题：1150

这道题是倍增LCA稍加变化形成的。可以知道，从结点x到结点y的距离一定是x与根距离-最近公共祖先与根距离+y与根距离-最近公共祖先与根距离。

只需要计算一遍LCA就完全可以解决这道题。

LCA的关键点在于：f[i][j]=f[f[i][j-1][j-1]，即f[i]的2^j个祖先=f[i]的第2^j-1个祖先的第2^j-1个祖先。

LCA的查询即先跳到相同深度，再一起往上跳，最后x和y的父亲就是LCA。

AC代码：

第二题：1151

这道题其实和第一题一模一样，但是要求用tarjan算法。

tarjan算法原理比较复杂，可以看这篇博客，这里仅给出代码（其实是因为我描述不清楚）

AC代码：