Problem 1010. Mart Master II

Brief description:

给定一个边权树，初始时，一些结点上已经建立了市场。每个结点会被距离自己最近的市场所支配（距离相同时，被标号最小的市场支配）。
。。。现在你可以新建一个市场，问新建的市场最多可以支配多少结点。

Analysis:

树分治。

。。。考虑每一个分治中心 c。。。
我们需要求出它对每个所有子树中的结点 u 的贡献（也就是有多少结点，在树中，经过 c，被 u 结点支配）

首先需要枚举新建市场的结点。对于所有结点。。求出距离其最近的市场的距离。。d[u]。。
（这一步把所有 mart 都扔到起始点的集合里。。用 Dijkstra 搞搞就行了。。
注意到距离相同的时候要取标号最小的。。所以这里的 d[u] 需要开 pair。。）

。。树分治的部分。。。需要三遍 dfs()。。
我们先 dfs0() 整棵子树…求出每个结点 u 到 c 的距离 dd，与 d[u] 比较。。
如果 d[u] < dd 那么舍弃。。否则加入平衡树。记做 all。。

.. 再 dfs1() 一个分支。。类似的。。得到 sub。。。
。。再 dfs2() 一个分支。。此时可以通过 all - sub。。。统计这个分支中所有结点的贡献。。。

（上面的平衡树也可以直接用 vector 排序后二分、、）。

http://vjudge.net/vjudge/problem/viewSource.action?id=2763104

Posted by xiaodao
Category: 日常