BZOJ 4712.洪水

首先考虑一个暴力的 DP:
fuf_u 表示以 uu 为根的子树内,要使得 uu 与所有叶子不连通,最小的需要删除的点的点权和。

fu=min(au,(u,v)Efv) f_u=\min(a_u,\sum\limits_{(u,v)\in E} f_v)

uu 没有儿子时右边那个和式当做 \infty 处理。

按照套路设一个 gug_u 使得

fu=min(au,fsonu+gu) f_u=\min(a_u,f_{\text{son}_u}+g_u)

定义 \otimes 为把乘法换成加法,加法换成取 min\min 的矩阵乘法。

[guau0][fsonu0]=[fu0] \begin{bmatrix} g_u&a_u\\ \infty&0 \end{bmatrix}\otimes \begin{bmatrix} f_{\text{son}_u} \\ 0 \end{bmatrix}= \begin{bmatrix} f_u\\ 0 \end{bmatrix}

树剖维护一下就 OK 了。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
#include <cstdio>
#include <algorithm>
#define ls (p << 1)
#define rs (ls | 1)
using namespace std;
const int N = 2e5;
int n,m;
int a[N + 5];
int to[N * 2 + 5],pre[N * 2 + 5],first[N + 5];
inline void add(int u,int v)
{
static int tot = 0;
to[++tot] = v,pre[tot] = first[u],first[u] = tot;
}
struct Matrix
{
long long a[2][2];
inline Matrix()
{
a[0][0] = a[0][1] = a[1][0] = a[1][1] = 0x3f3f3f3f3f3f3f3f;
}
inline Matrix(int)
{
a[0][0] = a[1][1] = 0,a[0][1] = a[1][0] = 0x3f3f3f3f3f3f3f3f;
}
inline Matrix(long long x,long long y)
{
a[0][0] = x,a[0][1] = y,a[1][0] = 0x3f3f3f3f3f3f3f3f,a[1][1] = 0;
}
Matrix operator*(const Matrix &o)
{
Matrix ret;
for(register int i = 0;i < 2;++i)
for(register int j = 0;j < 2;++j)
for(register int k = 0;k < 2;++k)
ret.a[i][j] = min(ret.a[i][j],a[i][k] + o.a[k][j]);
return ret;
}
};
Matrix seg[(N << 2) + 10];
void insert(int x,Matrix k,int p,int tl,int tr)
{
if(tl == tr)
{
seg[p] = k;
return ;
}
int mid = tl + tr >> 1;
x <= mid ? insert(x,k,ls,tl,mid) : insert(x,k,rs,mid + 1,tr);
seg[p] = seg[ls] * seg[rs];
}
Matrix query(int l,int r,int p,int tl,int tr)
{
if(l <= tl && tr <= r)
return seg[p];
int mid = tl + tr >> 1;
Matrix ret(1);
l <= mid && (ret = ret * query(l,r,ls,tl,mid),1);
r > mid && (ret = ret * query(l,r,rs,mid + 1,tr),1);
return ret;
}
int fa[N + 5],sz[N + 5],son[N + 5],top[N + 5],id[N + 5],ed[N + 5];
long long f[N + 5],g[N + 5];
void dfs1(int p)
{
sz[p] = 1;
for(register int i = first[p];i;i = pre[i])
if(to[i] ^ fa[p])
{
fa[to[i]] = p,dfs1(to[i]),sz[p] += sz[to[i]];
if(!son[p] || sz[to[i]] > sz[son[p]])
son[p] = to[i];
f[p] += f[to[i]];
}
if(!son[p])
f[p] = a[p];
else
f[p] = min(f[p],(long long)a[p]);
}
void dfs2(int p)
{
static int tot = 0;
id[p] = ++tot;
if(son[p])
top[son[p]] = top[p],dfs2(son[p]),ed[p] = ed[son[p]];
else
ed[p] = id[p],g[p] = 0x3f3f3f3f3f3f3f3f;
for(register int i = first[p];i;i = pre[i])
if(!id[to[i]])
top[to[i]] = to[i],g[p] += f[to[i]],dfs2(to[i]);
}
void update(int x)
{
for(;x;x = fa[x])
{
insert(id[x],Matrix(g[x],a[x]),1,1,n),x = top[x];
Matrix cur = query(id[x],ed[x],1,1,n);
g[fa[x]] -= f[x];
f[x] = min(cur.a[0][0],cur.a[0][1]);
g[fa[x]] += f[x];
}
}
int main()
{
scanf("%d",&n);
for(register int i = 1;i <= n;++i)
scanf("%d",a + i);
int u,v;
for(register int i = 1;i < n;++i)
scanf("%d%d",&u,&v),add(u,v),add(v,u);
top[1] = 1,dfs1(1),dfs2(1);
for(register int i = 1;i <= n;++i)
insert(id[i],Matrix(g[i],a[i]),1,1,n);
scanf("%d",&m);
char op;
for(;m;--m)
{
scanf(" %c%d",&op,&u);
if(op == 'Q')
{
Matrix ans = query(id[u],ed[u],1,1,n);
printf("%lld\n",min(ans.a[0][0],ans.a[0][1]));
}
else
scanf("%d",&v),a[u] += v,update(u);
}
}