关于树上的问题

学术版

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

RT。

给定一颗树,如何求树上相互之间距离小于 x 的点集,要求这个点集是满足要求中大小最大的。


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

时间复杂度 O(nq)


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

@0x28202e202e29 thx。


by litjohn @ 2024-10-02 21:13:10

@Fish_ht 考虑一种优化:每次dfs时不仅将遍历到的点加入当前点所在的点集中,也将当前点加入遍历到的点的点集中?


by Fish_ht @ 2024-10-02 21:13:16

@litjohn 也感谢。


by IntoTheDusk @ 2024-10-02 21:17:49

@Fish_ht DDP???


by Fish_ht @ 2024-10-02 21:18:48

@IntoTheDusk ????????????,Orz%%%。

DDP大佬出现了!


by IntoTheDusk @ 2024-10-02 21:21:47

@Fish_ht 首先假设是单次询问怎么做


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

@IntoTheDusk 私聊。


by IntoTheDusk @ 2024-10-02 21:22:36

@Fish_ht 单次询问可以DP吗


by Fish_ht @ 2024-10-02 21:23:57

@IntoTheDusk 树形DP应该可以?

f_{x,0/1} 表示 x 选或不选的最大集合?


上一页 |