SGU 507

给一棵树。。每个叶子节点有一个权值,对每一个非叶子节点求出其子树中两两对中最小的绝对值差。。
dfs一下。。可以用一个平衡树维护信息,合并就可以启发式插入,并维护最小绝对值差就可以了。。。
加个分析吧。。看上去暴力合并可能会很慢。。但实际上可以证明是很快的。。
你看一个点如果每被插入一次,它所在的树的大小至少*2。。那么它就最多被插入logn次,总共最多也就是nlogn。。实际上还没有nlogn次的。。可以证明插入的是n量级的。。
那么每次插入是logn的。。总算法也就是nlogn的了。。
Code:
ideone.com/3PjCARDF

3 thoughts on “SGU 507

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>