题目是:给一棵有根树,可以删掉一些子树,让剩下的树(整体)DFS序 = BFS序。要删最少结点,还要输出剩下树的 DFS 序。

我自己推出来几个点:

样例 n=6, 边: 1-2,1-3,2-4,4-5,4-6,答案是最少删 1 个(删 3),剩下树 DFS 和 BFS 都是 1 2 4 5 6。

我一开始觉得 DFS序 = BFS序 等价于树是一条链,但这里 4 有 5、6 两个儿子,树不是链,序列却一样。所以这个结论不对。

我试过只保留根到每个叶子的最长链,算出来是 2,但正确答案是 1,所以也不是简单地只保留一条链。

输出格式写的是两行:第一行是删点数,第二行是剩下连通块的 DFS 序列。但样例输出只有一行 1,第二行为空?还是说剩下只有一个连通块所以第二行可以不输出?

现在卡住了,想问:

DFS序 = BFS序 的充要条件到底是什么?

最少删点的贪心/DP 应该怎么做?

第二行要输出的 DFS 序列,是删完之后剩下树的 DFS 序吗?多个连通块怎么处理?

如果有大佬懂这题,麻烦讲讲思路,感谢!

1 条评论

  • @ 2026-8-16 18:22:17

    DFS 是什么?

    我问了豆包,他说你的样例根不确定,所以不能找到答案

    • 1

    信息

    ID
    147
    时间
    ms
    内存
    MiB
    难度
    10
    标签
    (无)
    递交数
    4
    已通过
    1
    上传者