almost 3 years ago

题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1065
分析:
很显然这是一棵树套上一个环。
首先我们得知道给定这样一个图的时候该怎么计算答案。
考虑每一个结点对答案的贡献。
设环长为,结点深度为,那么它对答案的贡献可以表示成这样的一个式子:

我们可以发现当环长一定的时候,越小,答案就越大,所以对于每一次操作都必定是将某一个点连向号结点。
我们枚举环从哪里开始分割,再设表示结点的深度为,其子树中共进行了次操作的最大贡献。方程见http://blog.csdn.net/whjpji/article/details/7593329 (其实是我的公式写的丑。。)
这道题的初始条件坑惨我了。。。难道是我的姿势有问题。。。
bzoj1065.cpp

← bzoj1064:[Noi2008]假面舞会 bzoj3295:[Cqoi2011]动态逆序对 →
 
comments powered by Disqus