Innumerable Ancestors 尺取 dfs序 lca

给一棵树,m次查询,每次查询给两个集合,从这两个集合中分别选一个结点,使得这两个结点的lca的深度最大考虑dfs序为3, 4, 5的三个结点,3和4的lca深度一定大于等于3和5的lca深度所以可以将查询集合按dfs序进行排序,然后双指针,使每一对dfs序接近的结点都做一次lca,取最深的即可。尺取的思想。
#include
#include
#include
#include

using namespace std;

const int N = 1e5 + 10;

int n, m;
vector G[N];
int dep[N], id[N], fa[N], tot;
int up[N][21];
int s1[N], s2[N];

void dfs(int from, int x)
{
id[

Innumerable Ancestors 尺取 dfs序 lca最先出现在Python成神之路

版权声明:
作者:Alex
链接:https://www.techfm.club/p/4934.html
来源:TechFM
文章版权归作者所有,未经允许请勿转载。

THE END
分享
二维码
< <上一篇
下一篇>>