某岛

… : "…アッカリ～ン . .. . " .. .
May 17, 2013

PKU Campus 2013

Problem F. Moles

Brief description:

… 动态维护一棵边权树, 支持单边修改。。（边权可以是负数）。。
。。以及询问两点之间的路径长度，询问某点到期子树内一点的路径长度的最大值。

Analysis:

… DFS 一遍。。得到。。
一个 Euler 序。。用来求 LCA 。。。
一个一进一出的 DFS 序 用来维护路径。。
。。需要区间求和、和区间求最大前缀和两类操作。。
。。这里我们选择线段树。

。。。线段树做第二问。。树状数组做第一问。。
。。线段树同时解决两问。。

External link:

http://poj.openjudge.cn/campus2013/

Posted by xiaodao
Category: 线上比赛

« | »

  • Archives

    open all | close all