HMF-have much fun Site
文章
标签
16
联系方式戳我~
阅
【题解】AT3912 Antennas on Tree
热度: loading...
有一棵 个节点的树，无边权。
选择 个点。树上每个点到这 个点的距离构成一个 维坐标。
求得最小的 使得每个坐标都不相同。
考虑随便设定一个节点为根。两个节点的坐标不相同当且仅当一个有两个及以上儿子的节点，其子树内没有被选定的点，因此其他点到他的两个儿子的距离都是相同的。
考虑选定两个节点之后，这两个节点之间的链都可以表示出来。因此选定两个节点后，如果两个节点可以向两端拓展，那么拓展之后表达的范围一定不会更小，因此选定的节点一定是原树中度数为 1 的叶节点。
考虑先选定所有的叶节点。同上，如果一个节点的度数大于 2 ，即其儿子大于 1，那么一定需要至少一个选定的节点。但是其有一个儿子可以不选，通过其他儿子中的点用排除法表示出来。因此每个度数大于 2 的节点可以提供一个不选的机会，dfs 搜索从每个叶子节点出来遇到的第一个度数大于 2 的节点，将其打上标记，之后用总的叶节点数减去打上标记的节点数量即可。
赏
