小胡同的诗

算法描述tarjan算法在求强联通分量效率十分高，核心思想是维护的dfn和low数组；而对于树上公共祖先问题也能离线地处理询问，算法复杂度O(n+q)O(n+q)O(n+q)。算法是：后序遍历树上的结点，每次的子孙结点的祖先集合合并到其父亲结点中（并查集），之后去查询当前结点是否有询问，有询问且两个点都已经访问过那么这个两个点的LCA是另外那个点的祖先。由于是后序遍历的缘故，当前结点和另外那个结...

题目链接：LeetCode235思路：根据BST的性质可以得到以下逻辑：当root介于p、q之间时，LCA(T, p, q) == root；否则LCA要往p、q所在的区间去搜索。/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * ...

算法描述根据上一个博客介绍的dfs序以及欧拉序能够把树上的点转为线性的区间点，从而可以用区间的数据结构去维护。根据欧拉序的定义，我们会发现树上任意两点的第一次出现位置之间必然夹带着lca的点，至于为什么可以画图理解一下，因为我们生成这个欧拉序时每次回溯就加一个点，而任意两点之间的搜索树一定是从lca开始往下搜，然后回溯再转而去搜另外一个点，所以lca就生成再两点的时间戳之间了。于是我们维护完欧...

**思路：**借助后序遍历的思想求解，链式存储递归求解。注意前缀权值在LCA点处扣的次数，如果归在一条路径上要扣一次，否则扣两次。#include <bits/stdc++.h>using namespace std;struct BiTree { int id; BiTree *lson, *rson; BiTree ():lson(NULL),rs...