想当年高中组织活动的时候我还专门写过 Tarjan 的流程和证明，如今已经忘的干干净净，原来的代码也找不到了，只能现写了。
总的来说就是利用一个栈，将每个访问到的点 push 入栈，在寻找的过程中记录两个值，一个是 dfn—— 它是第几个搜索到的，一个是 low—— 它能衍生的点中 dfn 最小的值。如果一个点 dfn==low 说明它本身就是最小的点，把它及它栈以上的点全部 pop 出来就行，因为它上面的点必定是与它形成强联通分量。我们不妨假设它上面的点有不是它强联通分量的，那么此点在回溯到它本身的时候只有两种情况，一是它本身是强联通最小的点，那么在找到此点时会把它上面的点全部 pop 出去，另一种是它不是最小点，那么在遍历的过程中总会到第一种情况把它排除。
Tarjan 程序是正确无误的，然后最后要跑一个拓扑，然鹅我不大会。luogu 上爆了 40pt，然后去看别人的题解秒懂。用拓扑可以优化掉 ans、Q、new_val 等等数组，估计就 80pt 了，然后我们还得用 dp 去解决菊花图这种类型的数据。
这道题还给人一个教训是，对于缩点的题，我们记录下每条路径的开始与结束去构造新图，没必要单独列个 Q 这种数组。
40pt 代码如下：
（其实会个 Tarjan 就行了吧）

LCA（Least Common Ancestors），即最近公共祖先，是指在有根树中，找出某两个结点 u 和 v 最近的公共祖先。 ——— 来自百度百科

对于一棵树来说，我们为了求它的最近公共祖先其实思路和快速幂是差不多的，我们不能直接一个个的向上查找，这样会使时间复杂度爆表，我们应当以 2^k 的速率往上找，这样可以使其时间复杂度降为 log 级别。
不得不说 luogu 上的题解实在是晦涩难懂，我能明白他们在寻找相同深度的点的时候使用 log 可以更快的找到，但是其实可以一层层的向上跳，可能时间复杂度常数上乘个 5 左右的数，但影响不大。（还是自己的代码好懂）
听说树链剖分也可以做，但这玩意写起来太麻烦了，我高中最快时写一遍也要半个小时（毕竟 100 多行）
总之，我们求 LCA 时首先找每个节点 2^i 的父亲，然后先将它们跳到相同的深度然后再同时向上跳，注意特判其中一个节点就是 LCA。

线段树是一种树状数据结构，它可以区间加减，区间乘除等一系列操作，用于处理那种可以合并状态的数据，在使用其 3 倍左右的空间的代价下使得其修改、查询、求区间和等等操作变得更加快捷。但与此同时，我们无法利用它处理类似于区间最长 01 序列此类问题，而且线段树代码冗长，其实很容易写错（也可能是因为我太菜了）。
我们将一组数据进行如下处理，每相邻的两个数据有一个父亲节点来记录其总的状态，然后再记录其相邻父节点的总的状态，以此类推，最终得到一个树状结构，我们从上到下依次编号 1-n，这棵树满足父节点 * 2 = 左节点，父节点 * 2+1 = 右节点，设每个父节点代表 l-r 区间的状态，则左区间为 l,(r+l)/2 , 右区间为 (r+l)/2+1,r。根据此性质我们可以对他们进行维护。
每当我们访问一个节点，我们保证此节点的值一定正确，并尽可能少的改变其子孙节点的值，让时间消耗尽可能的小，同时把 lazy 标记也就是本来应该加的数传递到下一节点。
第一颗树实现了区间加与查询，第二颗树实现了区间乘法，加法，判断其中的先后顺序，其实也大同小异。
第三颗树用于实现历史最大值这种操作，然而由于本人电脑跑不动 500mb 的程序，再加之修改起来有点麻烦，就写个大致正确的程序摆在这了。
如果要继续完善，那么需要记录次大值并对于 spread 函数进行修改，就这样吧，后面再来补。

Dijkstra 算法用于解决单源最短路问题，假设起始点为 S，在最开始我们可以知道 S 到某些点的距离，从中取出最小的一个，我们可以保证在我们取出这个最小值的时候不可能有任何路径可以更短的到达此点，，此过程使用了贪心的思想。每当我们找出一个这样的点就更新 S 到与此点相连的其它点的距离，我们每一次取点都保证取出的是最短的且未被访问的点，这就是 Dijkstra 算法。

# 结构的基本知识

结构是一个或者多个变量的几何，这些变量可能为不同的类型，为了处理的方便而将这些变量组织在一个名字之下。
结构可以拷贝、赋值、传递给函数，函数也可以返回结构类型的返回值，在 ANSI 标准中，自动结构和数组现在也可以进行初始化。

指针是一种保存变量地址的变量。在存储时，内存被分为一块一块的。每一块都有一个特有的编号。而这个编号可以暂时理解为指针，就像酒店的门牌号一样。

国庆回家的火车上读完了《小王子》这本书，对于自从高三结束以来一直没有再阅读纸质小说的我来说，这的的确确是一种很新鲜的感觉，让我讶异的发觉，原来阅读是这么一种充实而快乐的体验。当然，打游戏远比此要快乐的多，这也是没办法的事，但以后当我没办法玩手机，也不妨多看看书吧。

插值算法主要运用于在数学建模竞赛中，现有的数据极少，不足以支撑分析的进行，这时候就需要使用一些数学的方法
插值的作用，“模拟产生” 一些新的但又比较靠谱的值来满足需求

代码如下

TOPSIS 法 (Technique for Order Preference by Similarity to Ideal Solution)
可翻译为逼近理想解排序法，也称优劣解距离法
TOPSIS 法是一种常用的综合评价方法，其能充分利用原始数据的信息，其结果能精确的反映各评价方案之间的差距