LCA

acwing 1171距离(离线LCA)

题面题解(Tarjan——离线求LCA) 前置知识在线做法：读一个询问，处理一个，输出一个离线做法：读完全部询问，再全部处理完，再全部输出做法在深度优先遍历时，将所有点分成三大类 2号点 &#x…

【HNOI2016模拟4.13】a

Description 给出一棵n个节点的树，每个节点ai的范围在1~m，和q次询问，每次询问x到y的路径中小于/等于/大于k的数的个数。强制在线。 n,q<300000,m<150000 Solution 裸题，用来练模板。有两种做法，一种是主席…

POJ1330，Nearest Common Ancestors（LCA+RMQ/倍增/Tarjan）

LCA的裸题。LCA可以用三种方式求解，其中离线算法有Tarjan，在线算法有倍增，RMQ，个人觉得RMQ效率会高一点。有个博客讲解的很好，链接： https://blog.csdn.net/my_sunshine26/article/details/72717112 这里我…

【LOJ 2788】管道（树上差分）

管道题目链接：LOJ 2788 题目大意给你一个 n 个点 m 条边的无向图不一定连通，把每个连通块看做子图，求每一个子图的桥。 n 1e5 m 6e6 空间 16 MB 思路发现存不下所有的边，但是能存点。那考虑能不能在一棵生成树上面搞。 …

bzoj 1776: [Usaco2010 Hol]cowpol 奶牛政坛

Description 农夫约翰的奶牛住在N (2 < N < 200,000)片不同的草地上，标号为1到N。恰好有N-1条单位长度的双向道路，用各种各样的方法连接这些草地。而且从每片草地出发都可以抵达其他所有草地。也就是说，这些草地和道路构成了一种叫做树…

POJ3728，The merchant（倍增LCA+分治）

题意：有n个城市，有n-1条边使各个城市相互直接或间接连通，给出一件货物在各城市的价格w[n]，然后给出q个询问，每个询问有两个城市s,t，问从s到t的路径上买入卖出货物盈利的最大值。注意：在某个城市…

bzoj 1146: [CTSC2008]网络管理Network

Description M公司是一个非常庞大的跨国公司，在许多国家都设有它的下属分支机构或部门。为了让分布在世界各地的N个部门之间协同工作，公司搭建了一个连接整个公司的通信网络。该网络的结构由N个路由器和N-1条高速光缆组成。每个部门都有一个专属的路由器…

[51nod1766]树上的最远点对

Description 给出一棵n个点的树，每次询问编号在[a,b]中的一个点和编号在[c,d]一个点的最远距离。 n<10^5 Solution 我们知道，树上最远的距离是树的直径。然后，直径可以由两个点集中的直径的总共四个端点两两配对得到。于是我们就可…

LCA的最暴力解法—openjudge 1330

题目大意：给一棵树，给定两个点，找到他们的最近公共祖先题目分析：这个题目的查询只有一次，我们只需要用最暴力的方法去完成就可以了题目详解： 给定一棵树，我们想要找到他的最近公共祖先&…

星球联盟

题目描述在遥远的S星系中一共有N个星球，编号为1…N。其中的一些星球决定组成联盟，以方便相互间的交流。但是，组成联盟的首要条件就是交通条件。初始时，在这N个星球间有M条太空隧道。每条太空隧道连接两个星球，使得…

bzoj 1787: [Ahoi2008]Meet 紧急集合

题目大意：给你一棵N个节点的数，M个询问，每次询问三个节点，让你求出一个集合点，使得三个点到该点和最小，输出这个点和最小和。三个点两两求LCA。然后会至少有两个相同，不同的那个就是所求的点。…

bzoj 1977: [BeiJing2010组队]次小生成树

Description 小 C 最近学了很多最小生成树的算法，Prim 算法、Kurskal 算法、消圈算法等等。正当小 C 洋洋得意之时，小 P 又来泼小 C 冷水了。小 P 说，让小 C 求出一个无向图的次小生成树，而且这个次小生成树还得是严格次小的&…

2016多校训练Contest4: 1007 Treasure hdu5770

Problem Description?? has got a treasure map,the treasure map consists of N nodes,there are N-1 bidirectional roads, Each of them connects a pair of nodes,the N nodes are all connected by the N-1 bidirectional roads.?? can travel through the roads.Ther…

【算法】树上倍增 LCA

文章目录相关链接模板题目1483. 树节点的第 K 个祖先最近公共祖先LCA的求法练习题目2836. 在传球游戏中最大化函数值2846. 边权重均等查询扩展题目相关链接把相关链接放在最前面是因为，周赛遇到了几次，不会做。这才想起来学一下这个算法。【力扣…

Codeforces Round 294

E. A and B and Lecture Rooms Portal. 显然可以想到，对于两点间的最短路径 l l l，到两点距离相等的点一定为 l l l 的中点。如果 l l l 为偶数，则不存在这样的点。有上面的思路之后，可以得到其他到两点距离相等的点经过 …

HDU 5266 pog loves szh III [lca 倍增算法]

之前我们在面对一个查询的时候，直接采用最暴力的搜索去完成此工作，现在，当我们面对有很多组数据的时候，发现一个一个的查询效率实在是太慢了，所以我们采用了一种新的方式，那就是倍增这个题就是给定Q个查询…

LCA——最近公共祖先

LCA问题是指在一棵树中找到两个节点的最近公共祖先。最近公共祖先是指两个节点在树中的最近的共同祖先节点。例如，在下面这棵树中，节点 6 6 6和节点7的最近公共祖先是节点 3 3 3。 1/ \2 3/ \ / \4 5 6 7解决LCA问题的方法有很多种&#xff…

[leetcode] LowestCommonAncestor

LowestCommonAncestor 问题描述：给定一颗二叉树，和二叉树的两个节点，计算出这两个节点的最低公公祖先。解法1: 最低公公祖先可能出现的最高值就是根节点。我们找到从根节点到两个节点的路径，path1和path2.则两者一定是Y字型或者是…

hdu 2586 How far away ？ LCA 模板题

第一次做LCA的题目。题意就是在一棵树中， 询问每两点的距离。开始一看觉得用带权并查集就可以了，但是只能求出相对距离，无法判断其具体位置，所以需要找到共同祖先，所以在tarjan函数中就有了两个循环， 一…

HDOJ 2856 How far away ？

文章目录题目描述：输出格式：输入数据：输出数据：解析题目描述： There are n houses in the village and some bidirectional roads connecting them. Every day peole always like to ask like this “How far is it if I want to go from house A to house B”? Usually…

【NOIP2013模拟】Freda的传呼机

Description 给出一张n个点，m条边的无向联通图，和q次询问，每次询问x到y的最短路。 n,q<10^4,m<1.2*10^4 时限100ms 10% n<10^3,m<1.2*10^3 另外30% nm1 另外50% nm Solution 这题画风突然就变了。 10%暴力，3…

[bzoj3626][LNOI2014]LCA

Description 给出一棵树，q次询问，每次询问∑ilrdeep(lca(i,z))n,q<5*10^4Solution 这道题在线明显不可做。（在线A了的大犇请收下我的膝盖） 首先，我们来思考一下，一组询问怎么做？ 暴力的想…

BZOJ3331: [BeiJing2013]压力（点双连通分量+缩点+LCA+树上差分）

链接：https://www.lydsy.com/JudgeOnline/problem.php?id3331 题意：n个点，m条无向边，给出q个点对，问这n个点分别是多少点对的必经点。（两点本身也算也算。） 思路：显然&#xff0c…

POJ 1986 Distance Queries Tarjan算法求最近公共祖先+前向星

第一次尝试自己写博客，如果有什么不好的地方还请大家多多批评指正~传送门：POJ 1986题目大意： John是一个农场主，他的牛都懒散惯了，所以拒绝按照John所选的路走。John就想找一条最短的路。本题输入前半部分与“导航噩梦…

Snow的追寻

Description 给出一棵有根树，1为根。给出q次询问，每次询问x,y表示除x,y为根的子树外，剩下的树的直径的长度。 n,q<10^5 Solution 既然和子树有关，那么我们就维护树的dfs序。然后每个区间维护直径的长度。用线段树&…

花花的森林

题目描述花花有一棵带n 个顶点的树T，每个节点有一个点权ai。有一天，他认为拥有两棵树更好一些。所以，他从T 中删去了一条边。第二天，他认为三棵树或许又更好一些。因此，他又从他拥有的某一棵树中去除了一条边。如…

leetcode -- 235. Lowest Common Ancestor of a Binary Search Tree【区间，二叉搜索树特点】

题目 Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST. According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that ha…

POJ - 3694 Network（无向图+多重边+动态加边+边双连通分量+并查集+LCA）

链接：https://cn.vjudge.net/problem/POJ-3694 题意：每加一次边输出当前桥的个数。思路：先将原图边双连通分量求出（顺便求出桥（割边）的个数），并且将边双联通分量缩点。缩点之后重…

Codeforces Round #294 (Div. 2) E

题目大意：给你一棵有n个节点的树。再给你m个询问，每次询问A，B。问你树上到A,B距离相等的点有几个。这场DIV2为何这么水而且我竟然没报名参赛。。。这题直接用倍增LCA即可用son[]表示子节点个数求出A B的链长度然后求出链的中点X …

hdu 6200 mustedge mustedge mustedge

Problem DescriptionGive an connected undirected graph with nnodes and medges, (n,m≤105) which has no selfloops or multiple edges initially. Now we have qoperations (q≤105): ⋅1 u v: add an undirected edge from uto v; (u≠v&&1≤u,v≤n)⋅2 u v: cou…

bzoj 3910: 火车

Description A 国有n 个城市，城市之间有一些双向道路相连，并且城市两两之间有唯一路径。现在有火车在城市 a，需要经过m 个城市。火车按照以下规则行驶：每次行驶到还没有经过的城市中在 m 个城市中最靠前的。现在小 A 想知道火车经…

bzoj 1906: 树上的蚂蚁

Description Input Output Sample Input 1 3 1 2 1 2 3 1 3 1 3 2 3 1 1 1 2 3Sample Output 2HINT N< 100000 Source Play with tree By Amber 摘自Mektpoy的博客传送门→http://blog.sina.com.cn/s/blog_ab8386bc0101i146.html←传送门1、链有重合部分求(a,b)离c最近的点…

POJ1986，Distance Queries（LCA）

这道题可以用LCA做出来，虽然最短路可以做出来，但是询问次数很多，每询问一次就求一次最短路的话，时间开销是很大的。这里我是用LCA转化为RMQ求出来，需要注意的一点就是题所给的图可能不是连通的，所以在DFS的…

洛谷P1967 货车运输（倍增+LCA+生成树）

题意：有n座城市，m条道路，每条路有个限流w，有q次询问，询问x,y城市之间的一次性允许通过的最大流量是多少。题意不难理解，看起来也不难，可以用倍增LCA解决，但是此题有个难点&#xff…

Street

Description 给出n个点,m条有权边,现对于每一条边，你需要回答出包含这条边的最小生成树的总边权值。 n,m<2*10^5 Solution 题解和题意一样简洁系列。首先求出mst，然后对于每一条不在mst里面的边，相当于把它和mst中的一条边替换。若…

acwing 1172 祖孙询问(LCA)

题面题解定义向上标记法：O(n) 从 x 向上走到根节点，并标记所有经过的点再从 y 向上出发，当第一次遇到被标记过的节点就是最近公共祖先倍增法 : 询问O(logn) 预处理O(nlogn) dep[i] : 代表 i 节点的深度 ，记根节点的深度为 1…

蓝桥杯系列 - 2018国赛 -版本分支

非常明显的 LCA 问题，可以用倍增算法来解决。一些前期铺垫： 我们记节点v到根的深度为depth(v)。那么如果节点w是节点u和节点v的最近公共祖先的话，让u往上走(depth(u)-depth(w))步，让v往上走(depth(v)-depth(w))步，都将…

【done】剑指offer68：二叉树最近公共祖先

LCA（lowest common ancestor）问题力扣，【二叉搜索树】https://leetcode.cn/problems/er-cha-sou-suo-shu-de-zui-jin-gong-gong-zu-xian-lcof/description/ 【普通二叉树】https://leetcode.cn/problems/er-cha-shu-de-zui-jin-gong-gong-zu…

LC 2846. 边权重均等查询

2846. 边权重均等查询难度： 困难题目大意： 现有一棵由 n 个节点组成的无向树，节点按从 0 到 n - 1 编号。给你一个整数 n 和一个长度为 n - 1 的二维整数数组 edges ，其中 edges[i] [ui, vi, wi] 表示树中存在一条位于节点 …

最近公共祖先之LCA(知识整理+板子总结)

思路来源《挑战程序竞赛》（倍增欧拉序） 『图论』LCA 最近公共祖先_小坏蛋_千千的博客-CSDN博客（清晰的离线Tarjan） 算法一、倍增（在线O(nlogn)预处理，O(logn)查询） #include<bits/std…

洛谷 P3252 [JLOI2012] 树

读题就读趋势了，还以为是每个深度都可以选一个，然后深度升序就可以了，以为是个按深度的01背包。但是前面还说了是一条路径，路径是不能断开的。那就从每个点开始爆搜一次就好了。看了一下范围n<1e5，n^2爆搜理论上…

20231026刷题记录

CF519E A and B and Lecture Rooms Portal. sol. 注意数组大小。 CF1551D2 Domino (hard version) Portal. sol. 注意区分 n , m n,m n,m。

洛谷——P3884 [JLOI2009] 二叉树问题（最近公共祖先，LCA）c++

文章目录一、题目[JLOI2009] 二叉树问题题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1 提示基本思路： 一、题目 [JLOI2009] 二叉树问题题目描述如下图所示的一棵二叉树的深度、宽度及结点间距离分别为： 深度： 4 4 4宽度&…

PAT A 1151 AC代码（LCA问题的通法思路）

这题可以结合1143来学习理解。树LCA解法通法思路： 确保U、V均存在于树上后从根结点开始 1、若当前结点index的中序位置在U，V的中序位置之间，则当前结点index就是U、V的LCA 2、若U、V的中序位置均小于index的中序位置，index…

28.LCA问题

一、问题简介最近公共祖先简称 LCA（Lowest Common Ancestor）。两个节点的最近公共祖先，就是这两个点的公共祖先里面，离根最远的那个。为了方便，我们记某点集 S { v 1 , v 2 , … , v n } S\{v_1,v_2,\ldots,v_n\} S…

2018 BUPT Winter Training #3 Div.2

A - The order of a Tree 根据二叉搜索树的性质，我们知道key[Lchild[r]]≤key[r]≤key[Rchild[r]]，所以LDR遍历插入一定是同结构的最小字典序二叉搜索树指针版： #include <iostream> #include <cstdlib> using namespace s…