@[Akeryep](/user/141866) 那不就是一种类似邻接表, 一种类似前向星吗 ...
by Hydrate @ 2019-12-03 20:31:20
@[北辰yama](/user/244079) 对不起大佬我看岔了
by Akeryep @ 2019-12-03 20:37:04
啊这种存储方式节省空间。。就一个节点下面存第一个孩子,如果有第一个孩子就新搞一个节点然后把后继设置为原来的孩子吧,这个在空间紧凑的时候用,但是某些操作效率就变低,但是节省空间是真的省,用哈希表的话就要$O(\sigma n)$空间复杂度了。
by hly1204 @ 2019-12-03 20:51:14
@[hly1204](/user/242973) 原来如此多谢
by Akeryep @ 2019-12-03 20:55:32
@[hly1204](/user/242973) 为啥就节省空间了。。
怎么存不都是 $O(n)$ 的吗
不知道您在说啥。。
by hellomath @ 2019-12-03 23:37:03
@[Akeryep](/user/141866)
树形 DP 的时候也不需要这种东西啊。。
写普通的暴力合并 DP,只要每次只枚举到 size,就是 $O(n^2)$ 的了
by hellomath @ 2019-12-03 23:38:48
有的题会好写一些,比如那个清华数据结构的PA2-1
by noip @ 2019-12-04 14:25:39