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