某岛

… : "…アッカリ~ン . .. . " .. .
September 18, 2014

2014 ACM/ICPC Asia Regional Xi’an Online

Problem 1010. Mart Master II

Brief description:

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

Analysis:

树分治。

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

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

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

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

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

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