首页 > Color a Tree
头像 louhc
发表于 2019-08-27 21:29:11
思路 比较难的贪心题.首先,对于权值最大的节点(不算根节点),染了它的父亲之后的第一步肯定是先染它.因此可以将这两个点缩起来(反正染的步骤是连续的).下一步该怎么办呢?仍然是找权值最大的点,不过要稍加变换.假设缩起来的点的权值为,与第三者的权值比较,先染的话代价为,先染$的话代价为,作差后为,那么只 展开全文