almost 3 years ago

题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1063
分析:
不得不说这一年的题目挺好的。
其实这道题我开始想的时候朝各种线性方向去想,结果细节搞的快要崩盘了。。。结果发现题解不是线性的,雪崩。。。
我们知道树链剖分任意两点间的轻边数量在的范围内,既然树链剖分都可以做到,那么我们的最优解肯定在的范围内。由此我们可以想到一种方法。
表示结点的子树中“不便利值”,且与相连的有条重边的方案数。注意这里的不便利值不一定能达到,但是由于答案我们取的是最小值,如果不便利值不一定能达到,那么肯定就在之前就可以得出答案,因此这样是可以的。
方程就贴一个图:


bzoj1062.cpp

← bzoj1062:[NOI2008]糖果雨 bzoj1064:[Noi2008]假面舞会 →
 
comments powered by Disqus