Cruiying

LCA

2-sat(1) BSGS(2) dfs(2) dp(63) dp + 线段树(1) floyd(3) Hash(1) KM算法(1) Kruskal重构树(2) manachar(2) Mendix(4) tarjan(1) 中位数(1) 主席树(2) 二分(3) 分数规划(3) 前缀和优化dp(2) 单调栈(6) 单调队列(1) 单调队列优化dp(1) 博弈(2) 后缀数组(15) 字典树(1) 差分约束系统(1) 并查集(4) 异或(2) 思维(2) 思维题(4) 扩展欧几里得算法(1) 拉格朗日插值(2) 数论(8) 未归档(15) 构造(1) 枚举(1) 模拟(3) 模板(1) 水题(4) 矩阵加速(2) 线段树(3) 网络流(2) 莫比乌斯反演(2) 莫队(4) 蓝桥杯(1) 规律(2) 贪心(2) 输入输出(1) 题解(1)

/ 注册

全部文章 / LCA （共6篇）

树上的最短边 (LCA+倍增)

给定一棵包含N个节点的带权树，节点编号1~N。小Hi每次会给定树上两个节点的编号u和v，请你计算从u到v的路径上，哪条边的权值最小。请你输出最小的权值。输入第一行包含两个整数N和Q，代表节点数和询问次数。以下N行每行包含一个整数Pi, Wi，代表1~N的父节点的编号，以及(i, P[i])...

2019-09-23

0 623

P3379 【模板】最近公共祖先（LCA）

题目描述如题，给定一棵有根多叉树，请求出指定两个点直接最近的公共祖先。输入输出格式输入格式：第一行包含三个正整数N、M、S，分别表示树的结点个数、询问的个数和树根结点的序号。接下来N-1行每行包含两个正整数x、y，表示x结点和y结点之间有一条直接连接的边（数据保证可以构成树）。接下...

2019-04-18

0 536

P3379 【模板】最近公共祖先（LCA）

题目描述如题，给定一棵有根多叉树，请求出指定两个点直接最近的公共祖先。输入输出格式输入格式：第一行包含三个正整数N、M、S，分别表示树的结点个数、询问的个数和树根结点的序号。接下来N-1行每行包含两个正整数x、y，表示x结点和y结点之间有一条直接连接的边（数据保证可以构成树）。接下...

2019-04-18

0 378

牛客小白月赛13 F题

链接：https://ac.nowcoder.com/acm/contest/549/F 来源：牛客网小A这次来到一个景区去旅游，景区里面有N个景点，景点之间有N-1条路径。小A从当前的一个景点移动到下一个景点需要消耗一点的体力值。但是景区里面有两个景点比较特殊，它们之间是可以直接坐观光缆车通过...

2019-04-17

0 420

牛客小白月赛13 F题

链接：https://ac.nowcoder.com/acm/contest/549/F 来源：牛客网小A这次来到一个景区去旅游，景区里面有N个景点，景点之间有N-1条路径。小A从当前的一个景点移动到下一个景点需要消耗一点的体力值。但是景区里面有两个景点比较特殊，它们之间是可以直接坐观光缆车通过...

2019-04-17

0 410

桂林电子科技大学第三届ACM程序设计竞赛 D题

链接：https://ac.nowcoder.com/acm/contest/558/D 来源：牛客网小猫在研究树。小猫在研究树上的距离。给定一棵N个点的树，每条边边权为1。 Q次询问，每次给定a,b,c，请你输出a到b的路径上离c最近的点的编号。题意：给你一棵树，然后有Q次询问。每次给...

2019-04-16

0 414