bzoj 4712: 洪水 — 树链剖分优化dp

  • 2018-01-03
  • 0
  • 0

 

4712: 洪水

Time Limit: 15 Sec  Memory Limit: 256 MB

Description

小A走到一个山脚下,准备给自己造一个小屋。这时候,小A的朋友(op,又叫管理员)打开了创造模式,然后飞到
山顶放了格水。于是小A面前出现了一个瀑布。作为平民的小A只好老实巴交地爬山堵水。那么问题来了:我们把这
个瀑布看成是一个n个节点的树,每个节点有权值(爬上去的代价)。小A要选择一些节点,以其权值和作为代价将
这些点删除(堵上),使得根节点与所有叶子结点不连通。问最小代价。不过到这还没结束。小A的朋友觉得这样
子太便宜小A了,于是他还会不断地修改地形,使得某个节点的权值发生变化。不过到这还没结束。小A觉得朋友做
得太绝了,于是放弃了分离所有叶子节点的方案。取而代之的是,每次他只要在某个子树中(和子树之外的点完全
无关)。于是他找到你。

Input

 输入文件第一行包含一个数n,表示树的大小。

接下来一行包含n个数,表示第i个点的权值。
接下来n-1行每行包含两个数fr,to。表示书中有一条边(fr,to)。
接下来一行一个整数,表示操作的个数。
接下来m行每行表示一个操作,若该行第一个数为Q,则表示询问操作,后面跟一个参数x,表示对应子树的根;若
为C,则表示修改操作,后面接两个参数x,to,表示将点x的权值加上to。
n<=200000,保证任意to都为非负数

Output

 对于每次询问操作,输出对应的答案,答案之间用换行隔开。

Sample Input

4
4 3 2 1
1 2
1 3
4 2
4
Q 1
Q 2
C 4 10
Q 1

Sample Output

3
1
4

HINT

Source

首先考虑没有修改,统计每个点的dp值,我们可以记 h[] 表示所以儿子的dp值和

所以更新很显然dp[x]=min(w[x],h[x])

继续考虑修改操作,考虑如何更新祖先

因为只有加操作,所以分几种情况(我们记更新后该点儿子的dp值增加了v,即该点的h[]值会增加v)

  1. 加之前,dp[x]=w[x],所以加之后,该点的dp值不会变化,他祖先的dp值也同样不会被更新
  2. 加之前,dp[x]=h[x],加之后,仍是h[x],就是说明原先w[x]-h[x]>=v,我们就可以直接给他h[]值加上v
  3. 加之前,dp[x]=h[x],加之后,变成w[x],我们重新更新他的dp值,记录增加值,然后继续更新祖先

我们不难发现第3种情况最多有(n+m)次,因为只要被更新过,我们只能在更新他的w[]值之后才可能被更新

所以我们就可以使用树链剖分优化,线段树上维护区间(w[]-h[])的最小值mn,我们对于两个情况3 的点中间直接区间修改

然后就是如何找到情况3的点,我们可以在每条重链的线段树中二分,找到第一个mn值小于v的点

需要注意的是线段树按dfs序存储,所以靠右的点更接近当前点,所以我们应该先在右侧寻找

然后,就一直循环,直到出现情况1或者到根节点

这样时间复杂度O(nlog²n)

 


 

评论

还没有任何评论,你来说两句吧