关于树上的问题

Fish_ht @ 2024-10-02 21:03:27

by Fish_ht @ 2024-10-02 21:04:06

需要输出具体集合的元素，1\leq n,m\leq10^3。

by litjohn @ 2024-10-02 21:06:57

@Fish_ht 枚举每个点，假设它在点集中，暴力求解。

by litjohn @ 2024-10-02 21:08:04

@Fish_ht 等等，你说的是共有m次询问？！

by Fish_ht @ 2024-10-02 21:08:08

@litjohn 怎么暴力，求教\bx

by litjohn @ 2024-10-02 21:08:30

@Fish_ht dfs

by Fish_ht @ 2024-10-02 21:08:32

@litjohn 是的。

by Fish_ht @ 2024-10-02 21:09:10

@litjohn 恐怕要炸。

by litjohn @ 2024-10-02 21:09:24

@Fish_ht 但这样是 O(n^2q) 的，其中 n 为树的点数，q 为询问总数

by bsdsdb @ 2024-10-02 21:10:19

@Fish_ht 定义深度为每个点到根的距离。

结果肯定是一个点深度为 i，其余为 x-i. 枚举 i，选中一个深度为 i 的和所有深度小于等于 x-i 的（要求 2i\le x）。输出构造的话dfs即可。

by Fish_ht @ 2024-10-02 21:10:26

@litjohn 所以dfs到底咋搞，蒟蒻不会啊，你要枚举 n 个点选或不选吗？