建造军营
记得当时是抄的题解,现在感觉真的很显然。
显然在一个点双里面任意选择都是无限制的,所以直接缩点然后建出树,直接树 dp。
考虑子树内的贡献,发现一旦子树内有任何一个点被选就要考虑连通性。所以设 \(dp(i,0/1)\) 表示里面是否选择过点。
转移显然,初始化显然。考虑统计答案。
记得当时是抄的题解,现在感觉真的很显然。
显然在一个点双里面任意选择都是无限制的,所以直接缩点然后建出树,直接树 dp。
考虑子树内的贡献,发现一旦子树内有任何一个点被选就要考虑连通性。所以设 \(dp(i,0/1)\) 表示里面是否选择过点。
转移显然,初始化显然。考虑统计答案。
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.ryyt.cn/news/69748.html
如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈,一经查实,立即删除!