ACM培训——图论(一)ppt课件.ppt

《ACM培训——图论(一)ppt课件.ppt》由会员分享，可在线阅读，更多相关《ACM培训——图论(一)ppt课件.ppt（87页珍藏版）》请在三一办公上搜索。

1、图论（一）,四川大学ACM/ICPC集训队 李冠一2013.7,百度百科： 图论是数学的一个分支。它以图为研究对象。图论中的图是由若干给定的点及连接两点的线所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有这种关系。,何为图论,个人理解：图论是ACM/ICPC中经常出现的一类题目。多见于中档题，当然也有神题神模型。图论相对好入门，图的BFS/DFS遍历几乎一个没有算法基础的人也可以掌握。但是，当研究深入之后，实际上图论包含着许多艰深而复杂的理论。当然，对于大多数普通的ACMer来说，我们首先要做的就是熟悉基本算法、掌握常见模型、提高

2、建模思维。,Part 1 图的遍历,一、图的BFS遍历,算法步骤：1、用dis数组表示各点距离起点S的距离。disi=-1表示i点还未被访问。用mapij表示i点和j点之间是否有边。2、将diss初始化为0，将其它点的dis初始化为-1。将S点入队3、while（队列非空） 从队首出队一个元素u 对于所有跟u有边相连的点v: if(disv=-1) disv=disu+1; v入队 ,每个节点只会入队一次，也只会出队一次。时间复杂度O(V+E)。,基本性质：,如果遍历的是0-1边权图呢？,队列中的节点距起点的最短距离单调递增。且队首与队尾的最短距离差值不超过1,如果遍历的是1-2边权图呢？,1

3、-2边权图的BFS：把每条长度为2的边中间加一个点，拆成两条边,例题 1.1HDOJ 1180: 诡异的楼梯,题意：在一个地图上，有一些位置是空地，有些位置有障碍。还有一些位置有梯子，不过梯子的方向有的是横向，有的是竖向，且方向每分钟变化一次。求从起点到终点的最短时间。,解法： 每次最多有五种状态可以选择： 上、下、左、右、停留原地等待。设计状态时除了要保存距离以外，还要保存当前的时间是奇数还是偶数 这样才能在BFS时进行状态的转移,二、图的DFS遍历,算法步骤（以0-1边权图为例）：1、从某个节点开始，每次任选一个与它相邻的未访问节点访问下去2、直到当前节点的所有相邻节点都已经被访问过。3、

4、回溯到第一个未被访问过的节点,三、拓扑排序,概念引入：一个工程常被分为多个小的子工程，这些子工程被称为活动（Activity)，在有向图中若以顶点表示活动，有向边表示活动之间的先后关系，这样的图简称为AOV网。在AOV网中为了更好地完成工程，必须满足活动之间先后关系，需要将各活动排一个先后次序即为拓扑排序。,算法步骤,1.从有向图中选取一个没有前驱的顶点，并输出；2.从有向图中删去此顶点以及所有以它为尾的边；3.重复上述两步，直至图空。*如果图不空，但找不到无前驱的顶点，说明图中有环。,拓扑序列：v6 , v1 , v4 , v3 , v2 , v5,注意：拓扑序列可能不唯一,拓扑排序的应用,

5、判断一个有向图中是否有环。无环的图所有点都能进行拓扑排序。求DAG图最长路类似于课程安排问题的题目,Part 2生成树与最短路,最小生成树 定义,b,c,h,i,f,a,e,d,g,4,8,8,1,2,4,14,7,9,10,6,7,2,11,生成树：对于一个无向图，生成树是它的一个无回路的联通子图最小生成树：各边权值和最小的生成树,有向图的最小有向生成树？最小树形图,最小生成树,rim 算法 (复杂度O(n2)kruskal算法 (复杂度O(m*lg(m),Prim算法,贪心准则加入后仍形成树，且耗费最小始终保持树的结构Kruskal算法是森林算法过程从单一顶点的树T开始不断加入耗费最小的边

6、(u, v)，使T(u, v)仍为树 u、v中有一个已经在T中，另一个不在T中,Prim 算法过程,b,c,h,i,f,a,e,d,g,4,8,8,4,14,7,9,10,6,7,2,11,a,i,d,c,b,h,g,f,e,1,2,Krustal算法,kruskal 算法思想：贪心选取最短的边来组成一棵最小的生成树。具体做法：先将所有的边做排序，然后利用并查集作判断来优先选择较小的边，直到建成一棵生成树。,int kruskal () int ans=0; sort(edge.begin(),edge.end(); for(int i=0; iedge.begin(); i+) if(reu

7、nion(edge.u,edge.v) ans+=edge.w; return ans;,代码如下：,int findp (int x) return px=-1?x:px=findp(px);bool reunion (int x, int y) int px=findp(x); int py=findp(y); if(px=py) return false; ppx=py; return true;,Prim 和 Kruskal的区别,Prim和Kruskal的贪心策略是一样的，都是选取耗费最小的边：对于Prim，其选取的边(u,v)必有一个顶点已经被覆盖，另一个顶点未被覆盖。而对于Kru

8、skal,其选取的边(u,v)任意，只要这个边的加入不能使被覆盖的顶点构成回路。,生成树计数,对于有n个点的图，构造一个矩阵，使得：若i=j，aij=dexi。（dexi为节点i的度数）。否则，若点i和点j间有边相连，aij=-1。若无边相连，aij=0。然后求这个矩阵的行列式，得到的即是这个图的生成树个数。,最优比率生成树,有带权图G, 对于图中每条边ei, 都有benifiti(收入)和costi(花费), 我们要求的是一棵生成树T, 它使得(benifiti) / (costi), iT最大(或最小). 解法：二分 or 迭代,根的度数不超过K的最小生成树。解法：迭代,K度限制生成树,最

9、优比率生成树解法： 0-1分数规划设xi等于1或0, 表示边ei是否属于生成树.则比率r = (benifiti * xi) / (costi * xi), 0i= 0, 根据性质1,当z =0 时r最大.,单源最短路径问题,单源最短路径=Single Source Shortest Path，即在有向图（或无向图）中求解给定点到其他点之间的最短距离,算法：DFS算法Dijkstra算法Bellman-Ford算法SPFA算法,dijkstra算法,5、重复4、5直至所有的点都进入S,1、集合S，表示已经找到最短路径的点。dis表示各点当前据源点的最短距离2、初始时，集合中只有源点。,3、每个

10、点u进入集合S时，用disu+mapuv更新所 有与它相连的节点v的disv。4、选取S外的点中dis最小的一个点进入S,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,演示：求从1到8的最短路径,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X=1,min d12,d14,d16=min 0+2,0+1,0+3=min 2,1,3=1X=1,4, p4=1,p4=1,p1=0,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X=1,4,min d12,d

11、16,d42,d47=min 0+2,0+3,1+10,1+2=min 2,3,11,3=2X=1,2,4, p2=2,p1=0,p4=1,p2=2,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X=1,2,4,min d16,d23,d25,d47=min 0+3,2+6,2+5,1+2=min 3,8,7,3=3X=1,2,4,6, p6=3,p2=2,p4=1,p1=0,p6=3,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X=1,2,4,6,min d23,d25,c47,d67=min

12、2+6,2+5,1+2,3+4=min 8,7,3,7=3X=1,2,4,6,7, p7=3,p2=2,p4=1,p1=0,p6=3,p7=3,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X=1,2,4,6,7,min d23,d25,d75,d78=min 2+6,2+5,3+3,3+8=min 8,7,6,11=6X=1,2,4,5,6,7, p5=6,p2=2,p4=1,p1=0,p6=3,p7=3,p5=6,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X=1,2,4,6,7,min d2

13、3,d53,d58,d78=min 2+6,6+9,6+4,3+8=min 8,15,10,11=8X=1,2,3,4,5,6,7, p3=8,p2=2,p4=1,p1=0,p6=3,p7=3,p5=6,p3=8,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X=1,2,3,4,6,7,min d38,d58,d78=min 8+6,6+4,3+7=min 14,10,11=10X=1,2,3,4,5,6,7,8, p8=10,p2=2,p4=1,p1=0,p6=3,p7=3,p5=6,p3=8,p8=10,2,3,7,1,8,4,5,6,6,1

14、,3,4,10,5,2,7,5,9,3,4,6,8,2,X=1,2,3,4,6,7,8,1到8的最短路径为1，4，7，5，8，长度为10。,p2=2,p4=1,p1=0,p6=3,p7=3,p5=6,p3=8,p8=10,void dijkstra(int s, int t) ds=0; q.push(make_pair(s,0); while(!q.empty() int u=q.top().first; int temp=q.top().second; q.pop(); if(temp!=du) continue; for(int i=headu; i!=-1; i=nxti) int v

15、=toi; if(dv=-1|dvdu+wi) dv=du+wi; q.push(make_pair(v,dv); ,例题 2.1POJ 3463: Sightseeing,题意：求最短路的种数，及比最短路长度长1的路的总数,解法一：dijkstra时不止要记录最短路长度，还要记录最短路的种数，及比最短路长度少1的路的总数。每把一个点加入集合，更新disv的时候就要进行转移。当然，如果disv发生了变化。那么之前的计数要清零。,解法二：预处理起点和终点到每个点的最短距离。比最短路长1 的点，必定有且只有一条边不在最短路上。枚举。,那么，第K短路如何求呢？,先预处理出终点到每个点的距离，作为启发

16、函数。A*搜索时第k个被搜索到的节点的距离值即是第K短路的值,Dijkstra算法的局限性,如果边权为负值，Dijkstra算法还正确吗？求解右图A 至其他点的最短距离算法步骤：1）标记点A2）DistC=2最小，标记点C3）DistB=3最小，标记点B结束但是ShortestDistC=1,Dijkstra算法的局限性,下图中，A至F的最短路径长度是多少？,1,1,-1,-1,-1,-1,-,产生错误结果的原因,Dijkstra的缺陷就在于它不能处理负权回路：Dijkstra对于标记过的点就不再进行更新了，所以即使有负权导致最短距离的改变也不会重新计算已经计算过的结果,我们需要新的算法Bel

17、lman-Ford,Bellman-Ford算法思想,Bellman-Ford算法基于动态规划，反复用已有的边来更新最短距离Bellman-Ford算法的核心思想松弛Distu和Distv应当满足一个关系，即Distv=Distu+wu,v,Bellman-Ford算法流程,所有点i赋初值Disti= + ，出发点为s，Dists=0for k=1 to n-1for 每条边(u,v) 如果du!= + 且dvdu+wu,v则dv=du+wu,vfor 每条边(u,v) 如果du!= + 且dvdu+wu,v则存在负权回路,如果没有负权回路，那么任意两点间的最短路径至多经过n-2个点，因此经过

18、n-1次松弛操作后应当可以得到最短路径如果有负权回路，那么第n次松弛操作仍然会成功，这时，最短路径为-,应用：判断是否含有负环,时间复杂度,算法复杂度为O(VE)其中V=顶点数，E=边数我们知道Dijkstra的算法复杂度是O(V2)，经过优化的Dijkstra算法可以达到O(V+E)logE)所以Bellman-Ford算法并不比它快，但实际上Bellman-Ford算法也是可以优化的,Bellman-Ford算法的优化,在没有负权回路的时候，至多进行n-1次松弛操作会得到解，但实际上可能不到n-1次松弛操作就得到最优解了可以在每一轮松弛的时候判断是否松弛成功，如果所有的边都没有松弛的话，说

19、明Bellman-Ford算法已经可以结束了,进一步的优化SPFA算法,SPFA=Shortest Path Faster Algorithm也即Bellman-Ford算法的队列优化。初始时将源加入队列。每次从队列中取出一个元素，并对所有与他相邻的点进行松弛若某个相邻的点松弛成功，则将其入队。直到队列为空时算法结束。,void spfa(int s) memset(d,-1,sizeof(d); int front=0,rear=0; Qrear+=s; ds=0; while(front!=rear) int u=Qfront+;inqu=false; for(int i=headu; i

20、!=-1; i=nxti) int v=toi; if(dv=-1|dvdu+wi) dv=du+wi; if(!inqv) Qrear+=v; inqv=true; ,SPFA算法的优化,SLF(Small Label First)策略：设队首元素为i,队列中要加入节点j, 在djdi时加到队首而不是队尾, 否则和普通的SPFA一样加到队尾.,LLL(Large Label Last)策略:设队列Q中的队首元素为i，队列中距离标号的平均值为ave，每次出队时，若diave，把i移到队尾。,还可以用优先队列代替普通的FIFO队列,inq标志： 将要把一个节点入队时。如果一个节点已经在队伍中，那

21、么不必重复入队。 （1、节省时间 2、保证队列长度不超过n）,判负环时，用栈代替队列，或用迭代加深DFS代替BFS，可以取得明显的优化。,例题 2.2SOJ 4243: Saving Girl2012 SCU 光棍节欢乐赛,题意：有一张地图，经过某点会造成一定的伤害。问初始时最少有多少DP值，才能保证不半路阵亡。,解法：在某个点会获得x的伤害值，那么就由它向四周的格子各连一条长度为x的边。求最短路,差分约束系统,X0=0X0-X1=-1X1-X2=-5X2-X3=-3求X1,X2,X3最小值X1=1,X2=6,X3=9求解差分不等式组有什么好的方法吗？,与Bellman-Ford算法对比,前面

22、用到过Distv=-wu,v这与前面的不等式约束Xi-Xj=-k很类似，因此可以做如下转化：如果存在约束条件Xi-Xj=-k，则建立一条边由i指向j，权值为k，这样就把差分约束系统问题转化为最短路径问题了，然后利用Bellman-Ford算法求解,与Bellman-Ford算法对比,差分不等式组可能是没有解的，这实际上就对应了Bellman-Ford求解存在负权回路一般来说，求最小值要用最长路，求最大值要用最短路,题意：在区间0,50000上面有一些整数点。现给出50000个区间。并给出每个区间至少应覆盖多少个点。问这个区间上总共至少有多少个点,例题 2.3POJ 1201: Interval

23、s,解法： 如果用数组Si表示在0,i这个区间上面有多少个点，则题中输入数据ai,bi,ci可以表示为Sbi-Sai-1=ci除此之外还有隐含条件：Si+1-Si=0Si+1-Si=1,无向图从某点到其它点的最短路径一定会组成一棵最小生成树,无向图的生成树，每个点到根节点的路径都是最短路径,大家有没有觉得prim和dijkstra非常相似？,证明过程就是求解次小生成树的过程,全源最短路Floyd-Warshall算法,用法：求无负环图中任两点间的最短路。也可用于求最小环,void floyd() for(int k=0; kn; k+) for(int i=0; in; i+) for(int

24、 j=0; jn; j+) if(disik=-1|diskj=-1) continue; if(disij=-1|disijdisik+diskj) disij=disik+diskj; ,全源最短路Johnson算法,Johnson 算法主要用于求稀疏图上的全源最短路径。其主体思想是利用重赋权值的方法把一个原问题带负权的图转化为权值非负的图。然后再使用 N 次Dijkstra 算法以求出全源最短路。下面先介绍其重赋权值的主体步骤：1. 增设一点 S，由 S 往各点连一条权值为 0 的边。2. 使用 SPFA 求出 S 到各点 I 的最短路径 h(i)。3. 对于每条边 w(u,v),将其重

25、赋权为 w(u,v)=w(u,v)+h(u)-h(v)。,Johnson的重赋权思想也可解决最优调度问题和最小费用流问题,Part 3连通性,点连通度与边连通度在一个无向连通图中，如果有一个顶点集合，删除这个顶点集合，以及这个集合中所有顶点相关联的边以后，原图变成多个连通块，就称这个点集为割点集合。点连通度: 最小割点集合中的顶点数。如果有一个边集合，删除这个边集合以后，原图变成多个连通块，就称这个点集为割边集合。边连通度：最小割边集合中的边数。,如果一个无向连通图的点连通度大于1，则称该图是点双连通的，简称双连通或重连通。一个图有割点，当且仅当这个图的点连通度为1，割点集合的唯一元素被称为割

26、点，又叫关节点。,如果一个无向连通图的边连通度大于1，则称该图是边双连通的，简称双连通或重连通。一个图有桥，当且仅当这个图的边连通度为1，则割边集合的唯一元素被称为桥，又叫关节边。,割点与桥,割点,割边,双联通分支：在图G的所有子图G中，如果G是双连通的，则称G为双连通子图。如果一个双连通子图G它不是任何一个双连通子图的真子集，则G为极大双连通子图。双连通分支，或重连通分支，就是图的极大双连通子图。特殊的，点双连通分支又叫做块。,去掉任一割边/割点：图被分割成多个联通块,去掉所有割边：图被分割成多个双连通分支。（点双联通分支又称为“块”）割点也分割了双联通分支，但是割点是属于双联通分支的。,注

27、意：割点同时属于多个双联通分支，割边不属于双联通分支，其它点和边只属于一个双连通分支,求割点,原来路线替代路线环。移除一个点之后，经过改点的路线被截断了。要是沒有替代路线，无法绕过该点，就会不联通，该点就形成关节点。反过来说，如果有替代路线，该点就不会形成关节点。,要在一张图上找替代路线不太直接，但是找环就比较直接了把图重新画成树的形状，就容易找环了！要把图重新画成树的形状，利用DFS遍历就可以了。任取树上的一个点，当这个点的祖先与每一棵子树想要互通有无，利用父子边的话，显然会经过此点；另一方面，不想利用父子边的话，不想经过此点的话，就必须利用返祖边了。在 DFS树之中，子树与子树之间不会有边

28、，所以只需要考虑祖先与子树之间有没有 返祖边。这也就是说，祖先与每一棵子树之间都有 返祖边 的话，该点就不是关节点；祖先与其中一棵子树之间缺少 返祖边 的话，该点就是关节点。,定义DFS(u)为u在搜索树中被遍历到的次序号。定义Low(u)为u或u的子树中能通过非父子边追溯到的最早的节点，即DFS序号最小的节点。,一个顶点u是割点，当且仅当： (1) u为树根，且u有多于一个子树。 (2) u不为树根，且满足存在(u,v)为树枝边，使得DFS(u)=Low(v)。,一条无向边(u,v)是桥，当且仅当(u,v)为树枝边，且满足DFS(u)Low(v)。,Low(u)=min DFS(u) ，DF

29、S(v) (u,v)为后向边(返祖边) Low(v) (u,v)为树枝边(父子边) ,算法步骤：,求点双连通分支对于点双连通分支，实际上在求割点的过程中就能顺便把每个点双连通分支求出。建立一个栈，存储当前双连通分支，在搜索图时，每找到一条树枝边或后向边(非横叉边)，就把这条边加入栈中。如果遇到某时满足DFS(u)=Low(v)，说明u是一个割点，同时把边从栈顶一个个取出，直到遇到了边(u,v)，取出的这些边与其关联的点，组成一个点双连通分支。,求边双连通分支只需在求出所有的桥以后，把桥边删除，原图变成了多个连通块，则每个连通块就是一个边双连通分支。,例题 3.1NJUST 194: TWO N

30、ODES2013 南京赛区邀请赛,题意：给出一个无向图（V,E5000），问去掉两个点之后，这个图最多变成了几个连通块。,解法： 在求割点的过程中，若dfs树上的某子节点v的lowv=父节点的depu，显然这个点无法与树上的u点之上的点想通，在去掉u点后会断开。枚举其中一个点，在去掉这个点之后的图中做一次dfs， 算出去掉某个点之后断开的联通块数量。就可以求出去掉两个点之后剩下的联通块数量,例题 3.3POJ3352：Road Construction,题意：给一个无向图，问你需要添加多少条边之后这个图变成双连通分量。,具体方法为:首先把两个最近公共祖先最远的两个叶节点之间连接一条边，这样可以

31、把这两个点到祖先的路径上所有点收缩到一起，因为一个形成的环一定是双连通的。然后再找两个最近公共祖先最远的两个叶节点，这样一对一对找完，恰好是(leaf+1)/2次，把所有点收缩到了一起。,统计出树中度为1的节点的个数，即为叶节点的个数，记为leaf。则至少在树上添加(leaf+1)/2条边，就能使树达到边双连通。,Tarjan求SCC,下图中，子图1,2,3,4为一个强连通分量，因为顶点1,2,3,4两两可达。5,6也分别是两个强连通分量。,从节点1开始DFS，把遍历到的节点加入栈中。搜索到节点u=6时，DFN6=LOW6，找到了一个强连通分量。退栈到u=v为止，6为一个强连通分量。,Tarj

32、an求SCC,返回节点5，发现DFN5=LOW5，退栈后5为一个强连通分量。,Tarjan求SCC,返回节点3，继续搜索到节点4，把4加入堆栈。发现节点4向节点1有后向边，节点1还在栈中，所以LOW4=1。节点6已经出栈，(4,6)是横叉边，返回3，(3,4)为树枝边，所以LOW3=LOW4=1。,Tarjan求SCC,继续回到节点1，最后访问节点2。访问边(2,4)，4还在栈中，所以LOW2=DFN4=5。返回1后，发现DFN1=LOW1，把栈中节点全部取出，组成一个连通分量1,3,4,2。,Tarjan求SCC,题意：n头奶牛，给出若干个欢迎关系a b，表示a欢迎b，欢迎关系是单向的，但是

33、是可以传递的。另外每个奶牛都是欢迎他自己的。求出被所有的奶牛欢迎的奶牛的数目。,例题 3.2POJ 2186 popular cow,算法： 对有向图求强连通分量，然后将所有的强连通分量缩点。找到缩点后的图中无出度的点的个数，设为cnt, 若 cnt 1 , 则必无满足条件的点，因为一个出度为 零的点无法到达另一个出度为零的点；若cnt = 1 , 则该点所对应的强联通分量中的点的个数即为答案。,2-SAT,SATSatisfiability可满足性问题,第一个被证明为NP完全的问题,2-SAT: (SAT的特殊情况之一),简要步骤：,对于每个点i，建立两个节点，i和i,分别对应两个选项。如果

34、选择了i就必须选择j。那么就在连两条边：ij，ji。进行强联通缩点，如果某一对i和i处于同一个联通块中，则无合法方案。输出方案交替染色,2-SAT的对称性,对称性： i j 则 i j对称传递性： i j k 则 i j k路径的对称性： u v 则 u v,倍增法 (在线),Tarjan算法 (离线),LCA,在线与离线,在线算法：用比较长的时间作预处理，但是等信息充足以后每次回答询问只需要用比较少的时间离线算法：把所有的询问读入，然后一起把所有的询问回答完成例如：Fibonacci的在线算法复杂度为O(n+q)，离线算法复杂度为O(nlogq),Sparse Table算法,简称：ST算法

35、dpij表示区间i,i+2j-1的最小值，则dpi0=aidpij=mindpij-1,dpi+2(j-1)j-1这样可以得到所有的dpij,Sparse Table算法,如果询问区间为s,t，则只需要取k=(int)log2(t-s+1)RMQs,t=mindpsk,dpt-2k+1k这时候预处理的算法复杂度仅为O(nlogn)而回答问题仍然是O(1)的复杂度实际操作的时候，我们不一定用log来计算k，也可以通过二分查找。,goij代表i节点向根上的方向跳1j次的祖先,void dfs(int u) for(int t=0; tmapu.size(); t+) if(depmaput!=-1

36、)continue; int v=maput; depv=depu+1; gov0=u; for(int k=1; (1k)=depv; k+) govk=gogovk-1k-1; dfs(v); ,int LCA(int u,int v) if(depvdepu) swap(u,v); int jmp=depu-depv; for(int k=16; k=0; k-) if(jmpk,int k;for(k=16; k=0; k-)if(1k)depu),例题 4.1HDU 4718：The LCIS on the Tree2013 成都赛区邀请赛,题意：给出一棵树，每个点有一个权值。给定起点和终点，求两点间路径上，权值的最长连续递增子序列。,解法：对于每个LCA倍增区间区间维护六个量：最长左对齐递增，最长右对齐递增，最长递增最长左对齐递减，最长右对齐递减，最长递减 在求LCA过程中合并这些量,谢谢！,