POJ 2763"Housewife Wind"(DFS序+树状数组+LCA)

 

传送门

 

•题意

  一对夫妇居住在 xx村庄,给村庄有 $n$ 个小屋;

  这 $n$ 个小屋之间有双向可达的道路,不会出现环,即所构成的图是个树;

  从 $a_i$ 小屋到 $b_i$ 小屋需要花费 $w_i$ 时间;

  初始,女主角在 $s$ 号小屋,有 q 次询问,每次询问为以下两种的一个:

    • 0 u : 她有个孩子在 $u$ 号屋,需要妈妈接她回家,输出从 $s$ 到 $u$ 的最短时间
    • 1 x val : 由于种种原因,第 $x$ 条道路的耗时由之前的 $w_x$ 变为了 $val$

•题解

POJ 2763"Housewife Wind"(DFS序+树状数组+LCA)

  

  考虑如图所示的结构,在树上操作有些不便之处,所以,我们需要将其序列化;

  将上图所示的树,将其转化成 DFS序;

  $1\overset{w_{1,2}}{\rightarrow} 2 \overset{w_{2,4}}{\rightarrow} 4 \overset{-w_{2,4}}{\leftarrow} 2\overset{w_{2,5}}{\rightarrow}5\overset{-w_{2,5}}{\leftarrow}2\overset{-w_{1,2}}{\leftarrow}1\overset{w_{1,3}}{\rightarrow}3\overset{-w_{1,3}}{\leftarrow}1$

  并令权重沿叶子方向为正,沿根方向为负;

  那么从 $u$ 第一次出现的位置到 $v$ 第一次出现的位置中,不属于 $u,v$ 路径上的边就会被抵消掉;

  于是有:

    $(u,v)$之间的距离 = (从 $LCA(u,v)$ 到 $u$ 的边的权重和)+(从 $LCA(u,v)$ 到 $v$ 的边的权重和)

  因为是单点更新,所以,我们可以考虑到用树状数组来维护 DFS序;

上一篇:Loj #2687 - 「BalticOI 2013」Vim


下一篇:浅谈随机数的生成