题解 P7246 【手势密码】

whiteqwq · 2021-01-10 22:42:36 · 题解

P7246 手势密码解题报告：

更好的阅读体验

题意

• 给定一颗n个点带点权的树，可以用若干条简单路径覆盖树，使得每个点被覆盖的次数为它的点权。
• 数据范围：1\leqslant n\leqslant 3\times 10^6。

分析

非常神仙的贪心题。

考虑使用一种“帮忙”思想：对于以x为根的子树，我们将内部的点全部按要求覆盖，并从x延伸出v_x条路径来帮忙覆盖祖宗结点（某些路径也可以在x结点止步）。

因此我们做一遍树形dp，对于每个结点x，我们计算仅当前位置对答案的贡献，也就是说如果这里向上延伸出1条路径，那么贡献就加1；如果有两条路径在这里交汇或者一条路径在这里结束，那么贡献就减1（本来要两条路径，现在用一条路径就可以覆盖了）。

设x所有儿子组成了son(x)集合，那么很容易发现：

• 对于每一个y,z\in son(x)，y的路径可以和z的路径在x上连接起来（下文称之为匹配），这样就可以让y和z的两个操作变成一个操作，并可以让x多一次覆盖。
• 对于所有的儿子，两两之间匹配最多匹配\lfloor\frac{sum}{2}\rfloor次。
• 对于某个儿子y，满足v_y=maxx，那么我们发现如果其他的儿子都与y匹配（不考虑y不够的情况），那么最少也需要sum-maxx次匹配。

因此，在x结点上理论上可以进行l=\min\{\lfloor\frac{sum}{2}\rfloor,sum-maxx\}次匹配。

我们发现，在不增加x子树内对答案的贡献的情况下且不让x的覆盖次数超限的情况下，我们要减小匹配次数。因为我们减小匹配次数就可以让可以延伸出去的路径数更多，根据贪心的思想这样一定是更优的。

这里有一个问题，为什么要保证不增加x子树内对答案的贡献呢？延伸出去不是可以减小祖先对答案的贡献吗？

我们发现对于某一条路径，且当前子树的根的覆盖次数还没有满，那么如果它在这里匹配，那么会减小1的贡献；而如果延伸出去，只是有可能减小1的贡献（有可能匹配不到路径）。因此我们发现在当前子树能减小贡献我们直接匹配一定是不劣的。

我们设当前根结点为x，在x处的匹配次数为y，那么有y+(sum-2y)=a_x（y条在x处匹配的路径，其余的路径都向上延伸，共sum-2y条），也就是y=sum-a_x。

那么，我们当前子树最优匹配次数为match=\min\{l,a_x,sum-a_x\}。

知道了子树最优匹配次数，那么其他的都好算了。