LCA 好题！ 这道题我暂时只知道用Tarjan的解法。 Tarjan解法完美地运用了Tarjan的核心原理与性质： 深度优先搜索时的向下局部性。自己乱取得，蛤蛤蛤 题意： 给你一棵树，每个节点有一个权值。给你很多个询问，每个询问两个点。要你在给定点的树链上找到有序的最大差值。 思路： 首先考虑分治。设树链 u -> lca -> v 答案无非只有三种情况： 1. u -> lca 的最大差值 2. lca -> v 的最大差值 3. lca -> v 的最大值 – u -> lca 的最小值 考虑dp维护这四个值。 因为运用Tarjan算法的时候，基于dfs，在你的眼里，当前节点就是向下整棵树的根节点，你完全不会去考虑往上的节点。 所以你现在使用的四个值，刚好是你当前节点的孩子节点的最优值。 基于这个事实，…
昨晚疯狂掉分的第四题，其实比第三题还简单……
搞不懂cf又不按套路出牌了……先是来一个巨简单的，让每个人都不得不去签到，随后是坑题，然后是压轴题，再然后才是普通题，难题……
题意：
给你一棵树，每次询问3个点，要你求出3个点两两构成的路径中选出两条，使得他们相交的长度最长。
思路：
这道题并不难，先求出LCA，再分类讨论一下即可，但是但是但是但是！！分类的情况会非常非常多，就图而言就有4种，还要考虑各自的位置。
必须得总结一下，不然跟着写会疯掉。
考虑让每个点为两条路径的相交点，分三种情况讨论。
而每种情况中，当两个路径各自的lca相同时，除了该点的所在的路径以外只要求出另外两个点的lca长度 – 三点lca 路径长度即可。
否则，就只剩下第三个点为另外两点的父亲这一情况,所以长度为 根节点到所讨论的结点距离 减去 非父亲结点的另外两个结点的 lca 的距离。
AC Code
#include
本文起始请听我先说一句 ***的HDU4429!!!!!!!!! 这道题是我想自己写个LCA专题的起因。你要是去google题解的话全是用暴力求得。不知道为什么，你写题写到后面你会发现题解的代码全特么一个样子。说明他们很可能是不太懂，然后从某一个博客中看了代码，照样子写了，然后A了就得过且过的样子。当然我是不喜欢这样的。然后我就想用下tarjan求LCA，顺便复习一下算法。 结果！！！！ WA了两天！！！！ 忍无可忍交了一发暴力，60ms 秒过！！！！！玛德，这题绝对有问题！！！！我现在就要开个专题先验证一下我自己的算法。 先是放一下我对这题的题解 HDU 4429 Split the Rectangle 附带本人评价：狗屎 好题 题意： 给你一个矩形，再给你一些边，这些边用来分割矩形。 再是几次询问，每次询问给你两个点，要求你每次删去几条边，使得这两个点在同一个矩形中，问此时剩下的矩形数最多还有多少。 思路： 每次分割矩形后，使所形成的两个小矩形成文被分割矩形的两个孩子。如此这般就会形成一棵二叉树。 每次查询求出两个点所在的叶子节点，再…
LCA 即 最近公共祖先
对于一棵有根树，就会有父亲结点，祖先结点。
0
|
1
/ \
2 3
/ \
4 5
举几个例子 如图 这棵树的所有节点的根节点都是 0
但是
4 5 的LCA 是3
2 5的LCA 是1
1 3的LCA 是1
这里要介绍的 求最近公共祖先的算法是 Tarjan 算法 算法的核心思想在于 我们从一棵树的根节点开始向下深搜 当我们回溯的时候 我们才把两个集合合并 并更新根节点
这就意味着 对于一个节点 我们只有访问过他的所有子节点和他本身之后才更新他的根节点 我再简单点说 这样操作就实现了从叶子节点不断向上更新根节点 如果我们再更新之前完成记录LCA的操作 一切并迎刃而解
附上伪代码
…//parent为并查集，FIND为并查集的查找操作
//QUERY为询问结点对集合
//TREE为基图有根树
Tarjan(u)
换了个姿势还是上了HDU 据学长给我的图论题库来说 lca问题也写完了
这题几乎还是模板题 只不过是多了个 判断是否在同一棵树上 用了点小技巧 再Tarjan时 把根节点也传上去 如果得结果时根节点不同就跳过
另外这题灰常容易爆内存 稍微改了一下用 C++水过去了 然而G++还是爆………………
AC Code
#include