首页 > [ZJOI2008]骑士
开通博客写题解
头像 Henry_WYH
发表于 2021-10-14 19:24:52
做法1： 1.通过并查集维护连通性找出所有基环树的环的起点终点 2.对于每一个起点终点dfs不选这个点（和没有上司的舞会一摸一样的dfs），取max累加答案 #include<iostream> #include<cstdio> #include<algorithm&g 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 瑜画
发表于 2020-08-21 18:00:39
本题考察基环外向树上的树形dp首先需要找到环上的任意一条边，然后删去这条边，再对这条边的两个点进行树形dp，最后选择根节点都不选的最大值，就是最后的答案。根节点都不选的理由是：如果选上根结点，由于环上找出来的这条边切断了，所以在进行树形dp的时候，没有考虑切断的这条边上的另一个点，有可能把那个点选上 展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”