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
int dep[N], id[N], fa[N], tot;
int up[N][21];
int s1[N], s2[N];
void dfs(int from, int x)
{
id[
共有 0 条评论