【BZOJ4712】洪水(动态dp)

时间:2021-11-07 12:33:17

【BZOJ4712】洪水(动态dp)

题面

BZOJ

然而是权限题QwQ,所以粘过来算了。

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

题解

设\(f[i]\)表示从\(i\)出发走不到所有其叶子节点的最小代价。

显然\(f[i]=min(Val[i],\sum_vf[v])\),其中\(Val\)是删去这个点的权值,\(v\)是\(i\)的儿子。

换种写法的话,令\(g[i]\)表示已经考虑到的所有的儿子的\(f[i]\)之和,现在加入一棵新的子树\(v\)。那么就有\(f[i]=min(Val[i],g[i]+f[v])\),这种东西似乎可以直接写成矩阵的形式。

其中矩阵乘法是\(min\)和\(+\)的形式。

既然要支持动态修改,显然动态dp来维护。

考虑在重链上如何转移,首先我们设\(g\)是所有轻儿子的\(f[v]\)的和。设\(h\)表示\(i\)的重儿子。

那么转移方程就是\(f[i]=min(Val[i],g[i]+f[h])\)。

那么,我们只考虑重链上的转移,即

\(\begin{bmatrix}0&f[h]\end{bmatrix}\times\begin{bmatrix}0&Val[i]\\\infty&g[i]\end{bmatrix}=\begin{bmatrix}0&f[i]\end{bmatrix}\)

发现修改只会影响到\(g\)的值,那么直接改改就好了。

事实上那个\(\infty\)的位置随便写啥应该都没有问题的。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
using namespace std;
#define ll long long
#define MAX 200200
#define lson (now<<1)
#define rson (now<<1|1)
#define inf 1ll<<60
inline int read()
{
int x=0;bool t=false;char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-')t=true,ch=getchar();
while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
return t?-x:x;
}
int n;
struct Line{int v,next;}e[MAX<<1];
int h[MAX],cnt=1;
inline void Add(int u,int v){e[cnt]=(Line){v,h[u]};h[u]=cnt++;}
int dfn[MAX],ln[MAX],tim,fa[MAX],size[MAX],hson[MAX],top[MAX],bot[MAX];
void dfs1(int u,int ff)
{
fa[u]=ff;size[u]=1;
for(int i=h[u];i;i=e[i].next)
{
int v=e[i].v;if(v==ff)continue;
dfs1(v,u);size[u]+=size[v];
if(size[v]>size[hson[u]])hson[u]=v;
}
}
void dfs2(int u,int tp)
{
dfn[u]=++tim,ln[tim]=u;top[u]=tp;bot[u]=u;
if(hson[u])dfs2(hson[u],tp),bot[u]=bot[hson[u]];
for(int i=h[u];i;i=e[i].next)
if(e[i].v!=fa[u]&&e[i].v!=hson[u])
dfs2(e[i].v,e[i].v);
}
struct Matrix{ll s[2][2];}t[MAX<<2],tmp[MAX];
Matrix operator*(Matrix a,Matrix b)
{
Matrix ret;ret.s[0][0]=ret.s[0][1]=ret.s[1][0]=ret.s[1][1]=inf;
for(int i=0;i<2;++i)
for(int j=0;j<2;++j)
for(int k=0;k<2;++k)
ret.s[i][j]=min(ret.s[i][j],a.s[i][k]+b.s[k][j]);
return ret;
}
ll f[MAX],g[MAX],val[MAX];
void dp(int u,int ff)
{
f[u]=val[u];
if(hson[u])dp(hson[u],u),f[u]=min(f[u],f[hson[u]]);
else g[u]=inf;
for(int i=h[u];i;i=e[i].next)
if(e[i].v!=fa[u]&&e[i].v!=hson[u])
dp(e[i].v,u),g[u]+=f[e[i].v];
f[u]=min(f[u]+g[u],val[u]);
tmp[u]=(Matrix){0,val[u],inf,g[u]};
}
void Build(int now,int l,int r)
{
if(l==r){t[now]=tmp[ln[l]];return;}
int mid=(l+r)>>1;
Build(lson,l,mid);Build(rson,mid+1,r);
t[now]=t[rson]*t[lson];
}
void Modify(int now,int l,int r,int p)
{
if(l==r){t[now]=tmp[ln[l]];return;}
int mid=(l+r)>>1;
if(p<=mid)Modify(lson,l,mid,p);
else Modify(rson,mid+1,r,p);
t[now]=t[rson]*t[lson];
}
Matrix Query(int now,int l,int r,int L,int R)
{
if(l==L&&r==R)return t[now];
int mid=(l+r)>>1;
if(R<=mid)return Query(lson,l,mid,L,R);
if(L>mid)return Query(rson,mid+1,r,L,R);
return Query(rson,mid+1,r,mid+1,R)*Query(lson,l,mid,L,mid);
}
int GetVal(int x){return Query(1,1,n,dfn[x],dfn[bot[x]]).s[0][1];}
void Modify(int u)
{
while(u)
{
tmp[u]=(Matrix){0,val[u],inf,g[u]};Modify(1,1,n,dfn[u]);
u=top[u];if(u==1)break;
g[fa[u]]-=f[u];f[u]=GetVal(u);
g[fa[u]]+=f[u];u=fa[u];
}
}
int main()
{
n=read();
for(int i=1;i<=n;++i)val[i]=read();
for(int i=1;i<n;++i)
{
int u=read(),v=read();
Add(u,v);Add(v,u);
}
dfs1(1,0);dfs2(1,1);dp(1,0);Build(1,1,n);
int Q=read();
while(Q--)
{
char ch[3];scanf("%s",ch);
int u=read();
if(ch[0]=='Q')printf("%d\n",GetVal(u));
else val[u]+=read(),Modify(u);
}
return 0;
}

【BZOJ4712】洪水(动态dp)的更多相关文章

  1. BZOJ4712洪水——动态DP&plus;树链剖分&plus;线段树

    题目描述 小A走到一个山脚下,准备给自己造一个小屋.这时候,小A的朋友(op,又叫管理员)打开了创造模式,然后飞到 山顶放了格水.于是小A面前出现了一个瀑布.作为平民的小A只好老实巴交地爬山堵水.那么 ...

  2. 【bzoj4712】洪水 动态dp

    不难发现此题是一道动态$dp$题 考虑此题没有修改怎么做,令$f[i]$表示让以$i$为根的子树被覆盖的最小花费,不难推出$f[i]=min(\sum_{j∈son[i]} f[j],val[i])$ ...

  3. bzoj 4712 洪水——动态DP

    题目:https://www.lydsy.com/JudgeOnline/problem.php?id=4712 因为作为动态DP练习而找到,所以就用动态DP做了,也没管那种二分的方法. 感觉理解似乎 ...

  4. bzoj 4712 洪水 —— 动态DP

    题目:https://www.lydsy.com/JudgeOnline/problem.php?id=4712 设 f[x] = min(∑f[u] , a[x]),ls = ∑f[lson] 矩阵 ...

  5. BZOJ 4712 洪水 动态dp&lpar;LCT&plus;矩阵乘法)

    把之前写的版本改了一下,这个版本的更好理解一些. 特地在一个链的最底端特判了一下. code: #include <bits/stdc++.h> #define N 200005 #def ...

  6. &lbrack;bzoj4712&rsqb;洪水&lowbar;动态dp

    洪水 bzoj-4712 题目大意:给定一棵$n$个节点的有根树.每次询问以一棵节点为根的子树内,选取一些节点使得这个被询问的节点包含的叶子节点都有一个父亲被选中,求最小权值.支持单点修改. 注释:$ ...

  7. 【bzoj4712】洪水 树链剖分&plus;线段树维护树形动态dp

    题目描述 给出一棵树,点有点权.多次增加某个点的点权,并在某一棵子树中询问:选出若干个节点,使得每个叶子节点到根节点的路径上至少有一个节点被选择,求选出的点的点权和的最小值. 输入 输入文件第一行包含 ...

  8. 4712&colon; 洪水 基于链分治的动态DP

    国际惯例的题面:看起来很神的样子......如果我说这是动态DP的板子题你敢信?基于链分治的动态DP?说人话,就是树链剖分线段树维护DP.既然是DP,那就先得有转移方程.我们令f[i]表示让i子树中的 ...

  9. 动态 DP 学习笔记

    不得不承认,去年提高组 D2T3 对动态 DP 起到了良好的普及效果. 动态 DP 主要用于解决一类问题.这类问题一般原本都是较为简单的树上 DP 问题,但是被套上了丧心病狂的修改点权的操作.举个例子 ...

随机推荐

  1. Dinic 算法

    #include <bits/stdc++.h> using namespace std; ), M(1e5+); int head[N]; struct Edge{ /* r: resi ...

  2. javascript reverse string

    var strReversed = str.split('').reverse().join(''); function: function reverse(str){ return str.spli ...

  3. HttpClient&lpar;4&period;3&period;5&rpar; - Exception Handling

    HttpClient can throw two types of exceptions: java.io.IOException in case of an I/O failure such as ...

  4. hdu1664 bfs&plus;余数判重

    input n 不超过50个例子,n==0结束输入 Sample Input 7 15 16 101 0 output 最少个不同数字的n的倍数的x,若不同数字个数一样,输出最小的x Sample O ...

  5. Enterprise Architect 时序图

    添加时序图 1,在类图下面新建包 添加sequence时序图 点击流程控制,可以打开流程控制设计界面 我选择的是Lifeline线,你可以选择都差不多. 点击其中一条liftline连到其他上面 双击 ...

  6. &lbrack;BZOJ 3745&rsqb; &lbrack;COCI 2015&rsqb; Norma

    Description 给定一个正整数序列 \(a_1,a_2,\cdots,a_n\),求 \[ \sum_{i=1}^n\sum_{j=i}^n(j-i+1)\min(a_i,a_{i+1},\c ...

  7. 配置Nim的默认编译参数 release build并运行

    配置Nim的默认编译参数 release build并运行 默认情况下nim编译是debug build,如果需要release build, 需要加上-d:release , release编译的命 ...

  8. 15&period;selenium&lowbar;case03

    # 利用搜狗搜索接口抓取微信公众号 # 搜狗的微信搜索: # http://weixin.sogou.com # 搜索:“Python爱好者社区” # 找到它的微信号:python_shequ fro ...

  9. Linux设备驱动之Ioctl控制【转】

    转自:http://www.cnblogs.com/geneil/archive/2011/12/04/2275372.html 大部分驱动除了需要具备读写设备的能力之外,还需要具备对硬件控制的能力. ...

  10. git 推送出现 &quot&semi;fatal&colon; The remote end hung up unexpectedly&quot&semi; 解决方案

    本文转载于:https://blog.csdn.net/zcmain/article/details/76855595 https://blog.csdn.net/u012973744/article ...