企图get奖品然后喜闻乐见的T1傻逼了，于是就和奖品说拜拜拉
A.只要枚举超市走的顺序，然后发现是个无向图所以只要求k次最短路。
如果是有向图的话我们也可以把边全部反向一次spfa得到所有点到定点的最短路。
B.最小瓶颈树。考烂了已经。
C.这题其实并不难。
因为是选择两个点这样每个点的决策点就不能确定。
而我们首先就要找出此题的性质：最优解一定是一棵子树选择一个点走，其他的点选择一个点走。
这一点其实和 APIOT3 是一样的。
这个是显然的，而如果思考的时候没有想到这一点就可能滚粗了。
而一棵树的问题就是带权重心了。可以O（n）做。而这样是O（n^2）的。
我们考虑如何快速求出一棵子树的重心。
数据是随机的。所以树高是O（logn）的。
所以我们可以使用调整法，一开始把重心放在最高点上，然后不断沿着s[x]最大的儿子并且2*s[x]>tot走。这样我们的代价越来越小
最后一定走到重心。
这样复杂度是和树高相关的。所以是O（nlogn）的。
具体实现的时候只要预处理一个点最大的儿子和次大的儿子即可，因为切掉一棵子树有可能会使原来最大的儿子变小。
然后说一下重心相关的东西
重心是最大儿子最小的点。而且最大儿子s[x]一定满足2*s[x]<=n。
如何证明重心一定满足最大儿子2*s[x]<=n呢？并且除了重心以外的点都不满足这个性质呢?
我们可以从一个点出发不断沿着最大的儿子且满足2*s[x]>n的儿子走（显然这样的儿子只有一个）
然后每次走的时候这棵子树这个值都在减小。而且并不会产生走出来又走回来的情况（两个>号显然矛盾）
所以一定会到达一个最大儿子2*s[x]<=n的点。这个点就是我们要找的重心。
而这样走的过程，其实是所有点都某个点距离之和不断减小的过程。
需要注意的是：这样的带权重心与边权并没有关系。
不妨设重心为rt，然后它最大的儿子是x。
所以除了重心，所有的点必定都在重心的一个儿子中，所以这个点一定有一个儿子包含了重心除了该点所在的子树的点以外的所有其他点。
所以他一定存在一个儿子2*s[x]>n。
而我们发现从rt走到x减小的花费是n-2*s[x]。
所以我们从任意一个点开始沿着最大的儿子并且满足2*s[x]>n的儿子走，那么一定可以走到重心。
值得一提的是重心可能有两个，这时两个重心一定相邻。子树大小也很好算。
上面的取不取等让我很纠结，总之大概意思就是这样。
评论 (0)
