树剖在图结构中的应用

1/1树剖在图结构中的应用第一部分树剖概述：将树结构分解为链式结构的算法 2第二部分树剖应用：解决树结构的路径查询、子树查询等问题 4第三部分链式剖分：将树结构分解为链式结构的过程 8第四部分重链分解：将树结构分解为重链和轻链的过程 10第五部分树剖时间复杂度：预处理O(nlogn) 13第六部分树剖适用场景：树结构的路径查询、子树查询等问题 15第七部分树剖局限性：不适用于动态更新的树结构 17第八部分树剖扩展应用：可用于处理树结构上的其他问题 19

第一部分树剖概述：将树结构分解为链式结构的算法关键词关键要点【树剖概述：将树结构分解为链式结构的算法】

1.树剖定义：树剖（树剖分治）是一种将树结构分解为链式结构的算法，它通过将树上的边分为重边和轻边，然后将重边连接的子树重新排列，形成一条链式结构，从而实现对树结构的快速查询和修改。

2.树剖应用：树剖在图结构中有广泛的应用，例如：最近公共祖先查询、子树查询、动态规划、树上最长链查询、树上最短路径查询等。

3.树剖优势：树剖算法的优势在于其时间复杂度低，对于一个有n个节点和m条边的树，树剖可以在O(nlogn)的时间内完成预处理，并且对于后续的查询和修改操作，其时间复杂度均为O(logn)。

【树剖预处理：计算重边、轻边、子树大小】

#树剖概述：将树结构分解为链式结构的算法

定义

树剖，又称树链剖分，是一种将树结构分解为一系列链式结构的算法。它可以用于解决树上许多问题，例如最长路径、最近公共祖先和子树查询等。

树剖的原理

树剖的基本原理是将树分解为一系列链，这些链被称为重链。重链是一条从树根到某个叶子的路径，且路径上的每条边都是最重边（即权值最大的边）。树剖将树中的所有重链连接起来，形成一棵新的树，称为重链树。

树剖的算法流程

树剖的算法流程如下：

1.首先，需要对树进行深度优先搜索（DFS），以计算每个节点的深度和子树大小。

2.然后，需要找到每条重链的根节点。重链的根节点是子树大小最大的节点。

3.接下来，需要将每条重链连接起来，形成重链树。

4.最后，就可以利用重链树来解决树上的各种问题了。

树剖的应用

树剖是一种非常高效的算法，它可以用于解决树上许多问题。以下列举了一些树剖的应用：

*最长路径：树剖可以用于求解树上两点之间的最长路径。

*最近公共祖先：树剖可以用于求解树上两点最近公共祖先。

*子树查询：树剖可以用于查询某个子树内的信息，例如子树的总和、子树的最大值等。

*动态规划：树剖可以用于解决一些动态规划问题，例如树上背包问题。

树剖的复杂度

树剖的算法复杂度为`O(nlogn)`，其中`n`是树的节点数。这是因为树剖需要进行一次深度优先搜索，一次重链根节点的计算，以及一次重链树的构建。这些操作的复杂度都是`O(nlogn)`。

树剖的总结

树剖是一种非常高效的算法，它可以用于解决树上许多问题。树剖的原理是将树分解为一系列链，这些链被称为重链。树剖的算法流程包括深度优先搜索、重链根节点的计算和重链树的构建。树剖的复杂度是`O(nlogn)`。第二部分树剖应用：解决树结构的路径查询、子树查询等问题关键词关键要点树剖算法原理

1.树剖算法是一种适用于树结构的数据结构，它可以将一棵树分解成一系列的路径，这些路径可以被用来快速地查询树中的路径信息和子树信息。

2.树剖算法的基本思想是将树中的边分为重边和轻边，重边是连接两个子树的边，而轻边是连接子树内部的边。树剖算法通过将重边连接起来的子树形成一个新的树，称为剖分树。

3.树剖算法可以在O(nlogn)的时间内完成，其中n是树中的节点数。由于树剖算法可以将一棵树分解成一系列的路径，因此它可以被用来快速地查询树中的路径信息和子树信息。

树剖算法应用：路径查询

1.利用树剖算法，可以快速地查询树中任意两点之间的路径。具体来说，只需要找到两点所在子树的根节点，然后沿着重边往上跳，直到找到最近公共祖先，即可得到两点之间的路径。

2.树剖算法还可以被用来查询树中任意一条路径上的节点信息。具体来说，只需要找到路径两端节点的最近公共祖先，然后沿着路径从一端到另一端，即可得到路径上的所有节点信息。

3.树剖算法的路径查询时间复杂度为O(logn)，其中n是树中的节点数。因此，树剖算法可以非常高效地查询树中的路径信息。

树剖算法应用：子树查询

1.利用树剖算法，可以快速地查询树中任意一个子树的信息。具体来说，只需要找到子树的根节点，然后沿着重边往下跳，即可得到子树中的所有节点信息。

2.树剖算法还可以被用来查询树中任意一个子树的路径信息。具体来说，只需要找到子树的根节点，然后沿着重边往上跳，直到找到最近公共祖先，即可得到子树中的所有路径信息。

3.树剖算法的子树查询时间复杂度为O(logn)，其中n是树中的节点数。因此，树剖算法可以非常高效地查询树中的子树信息。

树剖算法应用：距离查询

1.利用树剖算法，可以快速地查询树中任意两点之间的距离。具体来说，只需要找到两点所在子树的根节点，然后沿着重边往上跳，直到找到最近公共祖先，即可得到两点之间的距离。

2.树剖算法还可以被用来查询树中任意一条路径的长度。具体来说，只需要找到路径两端节点的最近公共祖先，然后沿着路径从一端到另一端，即可得到路径的长度。

3.树剖算法的距离查询时间复杂度为O(logn)，其中n是树中的节点数。因此，树剖算法可以非常高效地查询树中的距离信息。

树剖算法应用：最短路径查询

1.利用树剖算法，可以快速地查询树中任意两点之间的最短路径。具体来说，只需要找到两点所在子树的根节点，然后沿着重边往上跳，直到找到最近公共祖先，然后从最近公共祖先沿着两点所在子树的重边往下跳，即可得到两点之间的最短路径。

2.树剖算法还可以被用来查询树中任意一条路径的最短路径长度。具体来说，只需要找到路径两端节点的最近公共祖先，然后沿着路径从一端到另一端，即可得到路径的最短路径长度。

3.树剖算法的最短路径查询时间复杂度为O(logn)，其中n是树中的节点数。因此，树剖算法可以非常高效地查询树中的最短路径信息。

树剖算法应用：连通性查询

1.利用树剖算法，可以快速地查询树中任意两个节点是否连通。具体来说，只需要找到两点所在子树的根节点，然后沿着重边往上跳，直到找到最近公共祖先，如果最近公共祖先存在，则两点连通，否则两点不连通。

2.树剖算法还可以被用来查询树中任意一条路径是否连通。具体来说，只需要找到路径两端节点的最近公共祖先，如果最近公共祖先存在，则路径连通，否则路径不连通。

3.树剖算法的连通性查询时间复杂度为O(logn)，其中n是树中的节点数。因此，树剖算法可以非常高效地查询树中的连通性信息。#一、树剖简介

树剖，全称“树链剖分”，是一种将树形结构分解成一系列链状结构的数据结构，可以优化对树形结构的查询和修改操作。树剖的定义是，对于一棵树，将其划分为若干个链，使得每个链上的节点数目尽量均匀，并且每个链上的节点都是连续的。

#二、树剖的算法

树剖的算法分为两个步骤：

1.重链剖分：

将树中所有节点按照深度从小到大排序，然后从根节点开始，依次考虑每个节点的子节点。对于每个子节点，如果它与父节点的深度差大于等于2，则将它们之间的边称为“重边”，将重边的子节点称为“重儿子”。然后，将重儿子作为新的根节点，继续上述过程，直到所有节点都被处理完毕。

2.轻链剖分：

将每个重儿子及其子树形成一条链，称为“重链”。对于每个重链上的节点，如果它不是重儿子，则将它与父节点之间的边称为“轻边”，将轻边的子节点称为“轻儿子”。然后，将轻儿子及其子树形成一条链，称为“轻链”。

#三、树剖的应用

树剖可以用于解决多种树结构的问题，包括：

1.路径查询：

给定两棵节点，求出它们之间路径上的所有节点。

2.子树查询：

给定一棵子树的根节点，求出子树中所有节点的和、最大值、最小值等信息。

3.动态规划：

利用树剖可以将一些树形结构的动态规划问题转化为链形结构的动态规划问题，从而降低算法复杂度。

4.图论：

树剖可以用于解决图论中的许多问题，如最小生成树、网络流、图着色等。

#四、树剖的复杂度

树剖的构建时间复杂度为O(nlogn)，其中n为树中节点的数目。查询和修改操作的时间复杂度为O(logn)，其中k为查询或修改操作涉及的节点数目。

#五、树剖的优缺点

树剖的优点包括：

1.查询和修改操作的时间复杂度为O(logn)，比暴力搜索的O(n)要快得多。

2.可以用于解决多种树结构的问题，如路径查询、子树查询、动态规划等。

树剖的缺点包括：

1.构建时间复杂度为O(nlogn)，对于大型树来说可能比较耗时。

2.树剖的结构比较复杂，实现起来可能比较困难。

#六、树剖的总结

树剖是一种非常重要的数据结构，可以用于解决多种树结构的问题。树剖的优点是查询和修改操作的时间复杂度为O(logn)，缺点是构建时间复杂度为O(nlogn)并且结构比较复杂。第三部分链式剖分：将树结构分解为链式结构的过程一、树剖概述

树剖，全称链式剖分，是一种将树形结构分解为链式结构的过程，常用于解决树上路径查询、子树查询等问题。

树剖的基本思想是将树形结构分解为若干条链，使得每条链上的节点都属于同一棵子树。这样，对于树上路径查询，只需要在链上进行查询，就可以得到结果；对于子树查询，只需要在子树所在的链上进行查询，也可以得到结果。

树剖是一种非常高效的算法，时间复杂度为O(nlogn)，其中n为树中节点的个数。

二、树剖的具体步骤

1.预处理：

首先，对树进行深度优先搜索（DFS），并记录每个节点的深度、父节点和子节点。

2.重链划分：

从根节点开始，依次考虑每个节点及其子节点。对于每个节点，如果其子节点中存在权值最大的子节点，则将该子节点作为重儿子。否则，将该节点标记为轻儿子。

3.轻链剖分：

对于每个轻儿子，将其与父节点连接成一条链。

4.子树剖分：

对于每个重儿子，将其子树递归地进行树剖。

三、树剖的应用

树剖可以用于解决树上路径查询、子树查询等问题。

#1.树上路径查询

对于树上路径查询，只需要在链上进行查询，就可以得到结果。具体步骤如下：

1.找到路径起点和终点所在的链。

2.在链上进行查询，计算路径长度或其他所需信息。

#2.子树查询

对于子树查询，只需要在子树所在的链上进行查询，就可以得到结果。具体步骤如下：

1.找到子树根节点所在的链。

2.在链上进行查询，计算子树大小或其他所需信息。

四、树剖的时间复杂度

树剖的时间复杂度为O(nlogn)，其中n为树中节点的个数。

树剖的预处理时间复杂度为O(nlogn)。这是因为，DFS需要访问每个节点一次，而重链划分和轻链剖分都需要对每个节点进行一次操作。

树剖的查询时间复杂度为O(logn)。这是因为，在链上进行查询只需要访问链上的一小部分节点。

五、树剖的应用实例

树剖可以用于解决许多树上的问题，例如：

*路径查询：计算两点之间的路径长度或其他信息。

*子树查询：计算子树的大小或其他信息。

*最长路径查询：计算树中两点之间的最长路径。

*最小生成树：找到树中的最小生成树。

*最小路径覆盖：找到树中的一组路径，使得这些路径覆盖所有节点，且路径长度最小。

树剖是一种非常高效的算法，在许多树上的问题中都有应用。第四部分重链分解：将树结构分解为重链和轻链的过程关键词关键要点【重链分解】：

1.重链分解的核心思想是将树结构分解成一系列重链和轻链，其中重链是树中边权最大的路径，轻链是连接重链的路径。

2.重链分解的过程是通过对树进行深度优先搜索，找到树中所有重链，然后将重链上的点作为重链的代表点，将轻链上的点作为轻链的代表点。

3.重链分解可以将树结构分解成一系列具有层次结构的链，使得在树结构上进行一些操作时可以更加高效，例如查询最长路径、最近公共祖先等。

【轻链】：

#重链分解：将树结构分解为重链和轻链的过程

#重链分解的由来

树剖（树链剖分）是将树结构分解为重链和轻链的过程，以便对树结构进行高效的处理。重链分解的提出可以追溯到上世纪90年代，当时，计算机科学家们正在研究如何对树结构进行快速查询和修改。他们发现，如果能够将树结构分解成若干个重链和若干个轻链，那么就可以对每条重链进行单独的处理，从而大大提高处理效率。

#重链分解的原理

重链分解的原理是将树结构中的节点按照一定规则分成若干个重链和轻链。重链是指包含最多节点的路径，而轻链则是连接重链的路径。

重链分解的过程如下：

1.首先，选择一个根节点。

2.然后，对根节点进行深度优先搜索（DFS），并记录每个节点的子树的大小。

3.选择子树最大的节点作为重儿子。

4.将重儿子及其子树形成一条重链。

5.将剩余的节点和边形成轻链。

6.重复上述步骤，直到所有节点都被划分到重链或轻链中。

#重链分解的应用

重链分解在图结构中有着广泛的应用，包括：

1.最长路径查询：在树结构中，查询两点之间的最长路径。

2.最短路径查询：在树结构中，查询两点之间的最短路径。

3.子树查询：在树结构中，查询某一节点的子树中的所有节点。

4.子树修改：在树结构中，修改某一节点的子树中的所有节点的值。

5.动态规划：在树结构上进行动态规划。

#重链分解的时间复杂度

重链分解的时间复杂度取决于树结构的结构和所要执行的操作。对于一棵具有$n$个节点的树，重链分解的时间复杂度通常为$O(n\logn)$。对于最长路径查询和最短路径查询，重链分解的时间复杂度通常为$O(\logn)$。对于子树查询和子树修改，重链分解的时间复杂度通常为$O(\logn)$。对于动态规划，重链分解的时间复杂度通常为$O(n\logn)$。

#重链分解的优缺点

重链分解是一种非常有效的树结构处理技术，具有以下优点：

*高效：重链分解可以将树结构分解成若干个重链和轻链，从而大大提高处理效率。

*简单：重链分解的原理简单，易于理解和实现。

*通用：重链分解可以应用于各种不同的树结构处理问题。

重链分解也有一些缺点，包括：

*空间复杂度高：重链分解需要存储重链和轻链的信息，这可能会导致空间复杂度较高。

*预处理时间长：重链分解需要对树结构进行预处理，这可能会导致预处理时间较长。

#总结

重链分解是一种非常有效的树结构处理技术，具有高效、简单和通用的优点。但重链分解也有一些缺点，包括空间复杂度高和预处理时间长。总体而言，重链分解是一种非常有用的技术，可以有效地处理各种不同的树结构问题。第五部分树剖时间复杂度：预处理O(nlogn)关键词关键要点树剖预处理的时间复杂度分析

1.树剖预处理的时间复杂度为O(nlogn)，其中n为树的节点数。

2.树剖预处理的目的是将树分解成若干个链，使得每个链的长度不超过logn。

3.树剖预处理的过程主要包括两个步骤：

-首先，计算每个节点的深度和子树大小。

-然后，将每个节点分配到一个链上，使得每个链的长度不超过logn。

树剖查询的时间复杂度分析

1.树剖查询的时间复杂度为O(logn)，其中n为树的节点数。

2.树剖查询的目的主要有两种：一种是查询两个节点之间的路径上的信息，另一种是查询某个节点的祖先节点的信息。

3.树剖查询的过程主要包括两个步骤：

-首先，将查询的两个节点分配到同一个链上。

-然后，在该链上进行查询。树剖在图结构中的应用——树剖时间复杂度：预处理O(nlogn)，查询O(logn)

在图结构中，树剖是一种用于高效查询树上节点间距离和最近公共祖先的算法。树剖的预处理时间复杂度为O(nlogn)，查询时间复杂度为O(logn)，其中n为树的节点数。

预处理过程：

1.将树转换为一棵重链剖分树。

2.在重链剖分树上进行深度优先搜索（DFS），为每个节点分配一个深度值和一个子树大小值。

3.计算每个重链的链顶节点，并将其存储在数组中。

4.计算每个节点到其重链顶节点的距离，并存储在数组中。

查询过程：

1.给定两个节点u和v，找到它们在重链剖分树上的最近公共祖先（LCA）。

2.计算u和v到LCA的距离。

3.计算u和v之间的距离，即u到LCA的距离加上v到LCA的距离。

时间复杂度分析：

预处理时间复杂度：

1.将树转换为重链剖分树的时间复杂度为O(nlogn)。

2.在重链剖分树上进行DFS的时间复杂度为O(n)。

3.计算每个重链的链顶节点的时间复杂度为O(n)。

4.计算每个节点到其重链顶节点的距离的时间复杂度为O(n)。

因此，树剖的预处理时间复杂度为O(nlogn)。

查询时间复杂度：

1.找到两个节点在重链剖分树上的LCA的时间复杂度为O(logn)。

2.计算u和v到LCA的距离的时间复杂度为O(logn)。

3.计算u和v之间的距离的时间复杂度为O(1)。

因此，树剖的查询时间复杂度为O(logn)。

应用场景：

树剖算法在图结构中有着广泛的应用，常见场景包括：

1.最长链查询：给定一棵树，查询树中包含指定节点的链的最大长度。

2.最短路径查询：给定一棵树，查询树中两个节点之间的最短路径长度。

3.最近公共祖先查询：给定一棵树，查询两个节点的最近公共祖先。

4.子树信息查询：给定一棵树，查询指定节点的子树中包含的节点数、边数、最长链长度等信息。

树剖算法凭借其高效的时间复杂度和广泛的应用场景，在图结构算法中占有重要地位。第六部分树剖适用场景：树结构的路径查询、子树查询等问题关键词关键要点【树剖在路径查询中的应用】：

1.树剖在路径查询中的核心思想是将树结构转化为一棵链，从而利用链式存储结构的查询效率优势进行路径查询。

2.树剖通过将树结构中相邻的点连接起来，形成一条连通路径，并通过子树的递归分解，将树结构转化为一系列不重叠的链。

3.在树剖中，每条链上相邻的点之间都存在父子关系或兄弟关系，因此可以通过链上节点的存储位置进行快速查询，从而实现高效的路径查询。

【树剖在子树查询中的应用】：

树剖适用场景：树结构的路径查询、子树查询等问题

树剖（树链剖分）是一种用于解决树结构中路径查询和子树查询问题的经典算法。它主要通过对树进行预处理，将树分解成若干条链，使得每个链上的节点都有一个对应的“轻儿子”，从而能够快速地查询两个节点之间的路径或子树中的信息。

#树剖的适用场景

树剖主要适用于需要在树结构中进行以下操作的问题：

*路径查询：计算两个节点之间的距离、最长公共祖先、路径上的权值和等。

*子树查询：计算子树中的节点个数、权值和、最深节点等。

*动态规划：在树结构上进行动态规划，如计算最短路径、最大独立集等。

*分治算法：将树结构划分为若干个子树，对每个子树进行分治处理，最后合并结果。

#树剖的优点

树剖具有以下优点：

*预处理时间复杂度为`O(nlogn)`，其中`n`为树的节点个数。

*查询时间复杂度为`O(logn)`，与树的高度成正比。

*可以处理动态树结构，即可以对树结构进行修改并重新计算结果。

#树剖的局限性

树剖也存在以下局限性：

*树剖算法只适用于树结构，不能用于处理其他类型的图。

*树剖算法需要对树进行预处理，因此不适合处理动态树结构，即无法快速地处理树结构的修改。

#典型应用场景

树剖在图结构中具有广泛的应用，以下是一些典型的应用场景：

*飞行员问题：在一个机场网络中，每个机场都是一个节点，相邻的机场之间有航班连接，需要计算两个机场之间的最短飞行距离。

*网络连通性：在一个计算机网络中，每个计算机都是一个节点，相邻的计算机之间有连线连接，需要判断网络是否连通。

*最短路径问题：在一个道路网络中，每个路口都是一个节点，相邻的路口之间有道路连接，需要计算两地之间的最短路径。

*最大独立集问题：在一个图中，需要找到一个最大的独立集，即一个没有两两相邻的节点的集合。

*树形动态规划：在树结构上进行动态规划，如计算最短路径、最大独立集等。

#总结

树剖是一种用于解决树结构中路径查询和子树查询问题的经典算法，具有预处理时间复杂度为`O(nlogn)`，查询时间复杂度为`O(logn)`的优点。树剖适用于各种树结构的路径查询、子树查询等问题，如飞行员问题、网络连通性、最短路径问题、最大独立集问题和树形动态规划等。第七部分树剖局限性：不适用于动态更新的树结构关键词关键要点树剖局限性：不适用于动态更新的树结构

1.树剖是一种静态树形结构分解算法，它将一棵树分解成一系列小的子树，以方便查询和修改树上的信息。

2.树剖在静态树形结构中非常高效，但它不适用于动态更新的树结构。这是因为树剖需要在树上进行预处理，而动态更新会破坏预处理的结果，从而导致树剖无法正确工作。

3.如果需要处理动态更新的树结构，可以使用其他更适合的算法，例如链式剖分或树状数组。

树剖的动态版本：链式剖分

1.链式剖分是一种动态树形结构分解算法，它可以处理动态更新的树结构。

2.链式剖分与树剖类似，都是将一棵树分解成一系列小的子树，但链式剖分在分解时使用了一种不同的策略，使其能够适应动态更新。

3.链式剖分在动态树形结构中非常高效，它可以支持各种常见的树上操作，例如查询子树信息、修改边权重、添加或删除节点等。

树剖的动态版本：树状数组

1.树状数组是一种动态树形结构存储算法，它可以处理动态更新的树结构。

2.树状数组使用一种特殊的数据结构来存储树上的信息，这种数据结构使得树状数组能够高效地支持各种常见的树上操作，例如查询子树信息、修改边权重、添加或删除节点等。

3.树状数组在动态树形结构中非常高效，它与链式剖分相比，具有实现简单、常数较小的优点，但它在某些情况下可能不如链式剖分高效。树剖局限性：不适用于动态更新的树结构

树剖算法是一种经典的树形结构数据结构，因其能高效地处理树形结构中节点之间的距离查询而被广泛应用于各种计算几何和图论算法中。然而，树剖算法也有其局限性，主要体现在以下几个方面：

1.不适用于动态更新的树结构

树剖算法在构建过程中需要对树形结构进行一次预处理，以生成一个二叉分解树，用于快速查找节点之间的距离。这个预处理过程的时间复杂度通常为`O(nlogn)`，其中`n`是树形结构中节点的数量。一旦树形结构发生变化，如增加或删除节点，则需要重新构建二叉分解树，这会产生额外的计算开销。因此，树剖算法不适用于频繁发生动态更新的树结构。

2.对树形结构的形状敏感

树剖算法的性能与树形结构的形状密切相关。对于高度平衡的树形结构，树剖算法能够快速地处理节点之间的距离查询，因为此时二叉分解树的高度较小。然而，对于高度不平衡的树形结构，树剖算法的性能可能会受到影响，因为此时二叉分解树的高度较高，导致查询路径上的节点数量较多。

3.空间复杂度较高

树剖算法在预处理过程中需要存储二叉分解树，这会占用额外的空间。二叉分解树的空间复杂度通常为`O(n)`，其中`n`是树形结构中节点的数量。对于大型树形结构，这可能会对算法的内存开销造成一定的影响。

综上所述，树剖算法在应用时应考虑到其局限性。对于动态更新频繁的树形结构，不适宜使用树剖算法。同时，对于高度不平衡的树形结构，树剖算法的性能可能会受到一定的影响。此外，在使用树剖算法时，也应注意其空间复杂度，以避免对内存造成过多消耗。第八部分树剖扩展应用：可用于处理树结构上的其他问题关键词关键要点【树剖扩展应用：最近公共祖先查询】

1.树剖可以用来解决最近公共祖先查询问题，即对于一棵树中给定的两个节点，找到它们最近的公共祖先。

2.我们可以使用树剖预处理出每个节点到根节点的路径，以及每个节点的子树信息。

3.在最近公共祖先查询时，我们可以通过遍历两个节点到根节点的路径，找到它们的最近公共祖先。

【树剖扩展应用：子树和查询】

#树剖在图结构中的应用：可用于处理树结构上的其他问题，例如最近公共祖先查询、子树和查询等

树剖扩展应用

1.最近公共祖先查询（LCA）：

给定一个树和一对节点，LCA查询旨在找到这两个节点的最近公共祖先，即在树中同时是这两个节点祖先的节点中最深的那个。借助树剖，我们可以预处理出所有节点到根节点的路径，并使用二叉