浅谈树上拓扑技巧（树上删点逃课神器）

· · 算法·理论

这里介绍一个非常实用的一个技巧，这个技巧是本人在学校的一次月赛中独创的，不排除存在先人智慧。本人已经用这个技巧 ac 了几个有着树形 dp，树上问题，却没有拓扑排序 tag 的题目（还有很多可以用这个技巧秒杀的题目题主没有去做）这个技巧就是 树上拓扑删点。

引入

首先相信大家都知道，在图论中，一个图的拓扑序列，就是该图进行拓扑排序后得到的序列。让我们回顾一下拓扑排序的过程（钦定本文章的边为无向边）：首先用队列维护一个度为 1 的点集，然后我们对这些点进行 bfs 删点，每次操作都会删除一个度为 1 的点，并枚举这些度为 1 的点所发出的 1 条边，同时继续将删除后度为 1 的点放入队列中。重复上述操作直至所有点删除完毕（显然如果遇到环，则会保留环不删除）。

现在我们在脑海假想一下拓扑排序过程，你想象到了什么？是不是就像从图的 最外围一点一点的删除，直到删完所有点或者遇见环。那么对于这样一个过程，接下来我们将它放到树上时，你就会知道它的魔力所在。

概念

回顾一类树上删点问题（或者可以转化为删点问题），是不是都类似于，进行删点之后，要求树上包含特定的部分，并且得到最优删点代价的同时，保留树的结构不被破坏？说到这里，相信大家已经开始拥有一个初步的结论了。没错，就是从 叶子节点，也就是拓扑序的最外围开始删点，显然不会破坏树的结构。并且我们仔细观察这类问题的题意，对于最优代价而言，不就是意味着，树上一定存在一个，进行 删点之后的最优树结构，而这个树的规模就是最优树规模。

证明

证明也非常简单，首先注意力从代价放到树结构这部分，最优代价不就是 删完点之后符合题目的树结构 所用的代价吗？考虑多删一个点，肯定不符合题目所要求的树结构；考虑少删一个点，肯定不是最优代价。并且因为我们是贪心从叶子节点进行删除，肯定不会破坏树结构。

证毕。

例题讲解

现在我们说一些简单的例题，以此来加深对这个技巧的印象。

例题 1

原题链接。

首先来看这道题的形式化题意：给出一颗树，并且给出一个点集，要求一颗包含该点集的最小子树，输出该子树大小。

题解里似乎都是树形 dp，dfs 等。这里我们可以用树上拓扑删点秒了这题。很显然这道题符合我们对树上拓扑删点的场景，即求一颗树中的一颗子树。那么很显然，我们可以贪心的从叶子节点删点，然后删到属于该点集的点直接跳过不处理改点，就做完了。

下面来看代码。

from collections import defaultdict,deque
n,k = map(int,input().split())
dli = [0] * (n + 1)
g = defaultdict(list)
for i in range(n - 1):
    u,v = map(int,input().split())
    g[u].append(v)
    g[v].append(u)
    dli[u] += 1
    dli[v] += 1
queue = deque()
for i in range(1, n + 1):
    if dli[i] == 1:queue.append(i)
visk = set(list(map(int,input().split())))
ans = 0
while queue:
    # 只需忽略即可
    if queue[0] in visk:
        queue.popleft()
    else:
        cur = queue.popleft()
        dli[cur] -= 1
        ans += 1
        for child in g[cur]:
            dli[child] -= 1
            if dli[child] == 1:queue.append(child)
print(n - ans)

例题 2

原题链接。

这到题的形式化题意是：给定一颗带点权的树，然后给定一个点集，可以任选起点，求最后经过这些点集之后返回起点的最小代价。

这道题是一个典型的树形 dp 题，题解也是树形 dp。但是很显然，我们可以将题意转换成：求树中的一颗子树，使得这颗子树的总权和最小。那么根据我们推导的结论，是不是就意味着，代价并不重要，重要的是，求这颗树中：包含给定点集的 最小树结构。那么很显然，我们只需要无脑的进行一个树上拓扑删点，然后删到属于给定点集的时候跳过不处理，最后输出这颗经过拓扑删点后的子树总权和（可以设答案为整颗树的总权，删点的时候也跟着减就行）即可。

例题 3

原题链接。

这里讲一下 cf 刚刚出的 c 题。观察题意，结合树上拓扑删点应用场景，是不是我们可以转换成，给定一颗树，求这颗树中的一颗满足最优结构的子树（注意子树可以是一个点）即可。有了这个结论，想一下，我们还需要先从起点走到终点吗？并不需要，我们只需要无脑的进行树上拓扑删点，并且跳过 end 节点，最后将 end 节点放到拓扑序最后输出即可。

接下来看下代码：

import math
import sys;input = lambda : sys.stdin.readline().rstrip()
from collections import defaultdict,deque
def solve():
    n,st,end = map(int,input().split())
    g = defaultdict(list)
    d = [0] * (n + 1)
    for i in range(n - 1):
        u,v = map(int,input().split())
        g[u].append(v)
        g[v].append(u)
        d[u] += 1
        d[v] += 1
    queue = deque([])
    for i in range(1,n + 1):
        if d[i] <= 1:queue.append(i)
    ans = []
    while queue:
        u = queue.popleft()
        # 显然遇到 end 节点就跳过不处理
        if u == end:continue
        d[u] -= 1
        ans.append(u)
        for v in g[u]:
            d[v] -= 1
            if d[v] == 1:queue.append(v)
    # 最后将 end 节点留到拓扑序最后即可
    ans.append(end)
    return ans

for i in range(int(input())):print(*solve())

扩展例题

大家可以尝试用这个技巧，去做一下相关的树形 dp 的例题。例如：黑白反转。注意要判断题目的做法是否符合该技巧的应用场景。

总结

树上拓扑删点这个技巧，适用于求树中满足最优子结构这类题，后面遇到一些树上问题时，不妨可以思考一下，是否可以用拓扑删点去作为这道题的突破口。

最后有一个思考的问题：树上拓扑删点，能否可以用于求树中不满足树结构的一部分呢？

如果这个技巧对你有帮助，不妨给本编一个点赞吧！