首页 > 编程语言 >lca算法

lca算法

时间:2023-06-02 16:44:42浏览次数:32  
标签:int d% dfs fa 算法 vector lca adj

#include <bits/stdc++.h>

using namespace std;

int main() {
  int n, m, s;
  scanf("%d%d%d", &n, &m, &s);
  
  int N = 20;
  vector<vector<int>> adj(n + 1);
  for (int i = 1; i < n; i++) {
    int u, v;
    scanf("%d%d", &u, &v);

    adj[u].push_back(v);
    adj[v].push_back(u);
  }
  
  vector<int> dep(n + 1);
  vector<vector<int>> fa(n + 1, vector<int>(N + 1));

  function <void(int)> dfs = [&](int u) {
    for (auto v : adj[u]) {
      if (v == fa[u][0]) {
        continue;
      }
      dep[v] = dep[u] + 1;
      fa[v][0] = u;
      dfs(v);
    }
  };

  dfs(s);
  
  // init
  for (int i = 1; i <= N; i++) {
    for (int j = 1; j <= n; j++) {
      if (fa[j][i - 1]) {
        fa[j][i] = fa[fa[j][i - 1]][i - 1];
      }
    }
  }

  while (m--) {
    int x, y;
    scanf("%d%d", &x, &y);
    if (dep[x] < dep[y]) {
      swap(x, y);
    }

    int z = dep[x] - dep[y];
    for (int j = 0; j <= N && z; j++, z /= 2) {
      if (z & 1) {
        x = fa[x][j];
      }
    }
    if (x == y) {
      printf("%d\n", x);
    } else {
      for (int j = N; j >= 0; j--) {
        if (fa[x][j] != fa[y][j]) {
          x = fa[x][j], y = fa[y][j];
        }
      }
      printf("%d\n", fa[x][0]);
    }
  }
}

标签:int,d%,dfs,fa,算法,vector,lca,adj
From: https://www.cnblogs.com/hacker-dvd/p/17452221.html

相关文章

  • 装饰器补充(算法)
    算法之二分法就是将一个列表或(其他容器)里面的数排列组合,将要找里面的数的时候从中间切分比较留半,然后再重复,最终至找到或者最后切分为空1x=[11,2,3,44,55,66,77,88,99,100,23,34,45,56,67]2x.sort()3defbijiao(l):4iflen(l)==0:5......
  • 算法刷题记录:日历中的数字
    题目链接https://ac.nowcoder.com/acm/contest/19859/B题目分析很简单的一道数位统计的题目其中年和月是乘法原理。(固定住年和月,枚举该月有几天,所以是乘法原理)当x=0并且month<10时,月需要特判一位数的情况,是加法原理日是加法原理AC代码//Problem:日历中的数字//Cont......
  • 强化学习基础篇【1】:基础知识点、马尔科夫决策过程、蒙特卡洛策略梯度定理、REINFORCE
    强化学习基础篇【1】:基础知识点、马尔科夫决策过程、蒙特卡洛策略梯度定理、REINFORCE算法1.强化学习基础知识点智能体(agent):智能体是强化学习算法的主体,它能够根据经验做出主观判断并执行动作,是整个智能系统的核心。环境(environment):智能体以外的一切统称为环境,环境在与智能体......
  • 强化学习基础篇[2]:SARSA、Q-learning算法简介、应用举例、优缺点分析
    强化学习基础篇[2]:SARSA、Q-learning算法简介、应用举例、优缺点分析1.SARSASARSA(State-Action-Reward-State-Action)是一个学习马尔可夫决策过程策略的算法,通常应用于机器学习和强化学习学习领域中。它由Rummery和Niranjan在技术论文“ModifiedConnectionistQ-Learning(MCQL)......
  • 算法题分析:反转整数
    最近刷到了一道medium难度的算法题,比较典型,可以用语法特性和常规解法来解决。题目如下:给定一个32字节的有符号整型数字x,将x反转过来返回。如果反转x会让其数值超出32位有符号整型数字范围[-2^31,2^31-1],那么就返回0。假设运行环境不允许你存储64位整型数字(有符号或者无符号)。......
  • Hazelcast的ManagedService接口类执行顺序
    在Hazelcast中,ManagedService接口中定义的方法的执行顺序如下:init(NodeEnginenodeEngine,Propertiesproperties):此方法在服务初始化时调用,允许你执行一些初始化逻辑或设置。reset():此方法在服务重置时调用,允许你重置或清理服务的状态。partitionLost(intpartitio......
  • hazelcast的NodeExtension接口类所有定义的方法分析
    在Hazelcast中,NodeExtension接口是一个扩展点,用于自定义和定制节点级别的行为。它定义了以下方法:voidbeforeStart(Nodenode,Propertiesproperties)此方法在节点启动之前调用。它允许你在节点启动之前执行一些自定义逻辑或设置。node:当前节点的Node对象。properties:......
  • 算法——字符串(一)
    1、给定一个字符串 s ,请你找出其中不含有重复字符的 最长子串 的长度。1classSolution{2publicintlengthOfLongestSubstring(Strings){3intlen=s.length();4intmax=0;5intright=0;6Set<Character>set=new......
  • 最短路与生成树算法
    写在前面最短路部分的代码还是3月的,奇丑无比,大家见谅……最短路单源最短路径首先我们介绍一些基本概念。由于是单源最短路,我们定义一个起点\(s\),\(dis_u\)表示起点\(s\)到节点\(u\)的最短路长度。一般来讲,对于一条为\(w\)的边\(u\tov\),如果目前的最短路是正确......
  • 代码随想录算法训练营第二十三天|669. 修剪二叉搜索树
    [参考链接]669.修剪二叉搜索树 [代码]1#Definitionforabinarytreenode.2#classTreeNode(object):3#def__init__(self,val=0,left=None,right=None):4#self.val=val5#self.left=left6#self.right=right......