【树剖+线段树维护DP】洪水

动态规划DP, 树链剖分, 线段树

传送门：BZOJ4712

思路：

  • 考虑朴素的DP：

  • $$ f_u=min(val_u,\sum f_v) $$

  • 树剖以后，可以维护$fL_u=\sum f_{Lv}$表示$u$的轻儿子DP值之和；

  • 那么可以得到：

  • $$ f_u=min(val_u,fL_u+f_v) $$

  • 我们可以定义一条重链上的转移$trans_{a,b}(x)$，令$a=val_u,b=Lf_u,x=f_v$；
  • 则转移可以表示为$trans_{a_1,b_1}(trans_{a_2,b_2}(\cdots))$；
  • 可以发现：

$$ trans_{a1,b1}(trans_{a2,b2}(x)) $$

$$ =trans_{a_1,b_1}(min(a2,b2+x)) $$

$$ =min(a_1,b_1+min(a_2,b_2+x)) $$

$$ =min(min(a_1,b_1+a_2),b_1+b_2+x) $$

$$ =trans_{min(a_1,b_1+a_2),b_1+b_2}(x) $$

  • 也这就是这个转移是封闭的，滋磁结合律；

  • 所以可以用线段树大力维护转移和修改。

注意：

  • 要开long long。

代码如下：

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
#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define N 300000
#define INF 0x3f3f3f3f3f3f3f3fLL
LL n,m,x,y,fa[N],sz[N],top[N],but[N],dfn[N],head[N],tot,clk,c[N];
char ch;
bool mk[N];
struct edge{LL v,nxt;}e[N*2];
void adde(LL x,LL y){e[++tot].v=y; e[tot].nxt=head[x]; head[x]=tot;}
struct trans{
	LL a,b;
	trans():a(0),b(0){};
	trans(LL a,LL b):a(a),b(b){};
	trans operator + (const trans t) const{
		return trans(min(a,b+t.a),min(b+t.b,INF));
	}
	LL calc(){return min(a,b);}
}seg[N*4];
#define ls x<<1
#define rs x<<1|1
void mdf(LL x,LL l,LL r,LL k,trans tmp){
	if (l==r){seg[x]=tmp; return;}
	LL mid=(l+r)>>1;
	if (k<=mid) mdf(ls,l,mid,k,tmp);
	else mdf(rs,mid+1,r,k,tmp);
	seg[x]=seg[ls]+seg[rs];
}
trans qry(LL x,LL l,LL r,LL L,LL R){
	if (l>=L && r<=R) return seg[x];
	LL mid=(l+r)>>1;
	if (L<=mid){
		if (R>mid) return qry(ls,l,mid,L,R)+qry(rs,mid+1,r,L,R);
		else return qry(ls,l,mid,L,R);
	}
	else return qry(rs,mid+1,r,L,R);
}
#undef ls
#undef rs
void dfs1(LL u){
	sz[u]=1;
	for (LL i=head[u],v;i;i=e[i].nxt)
		if ((v=e[i].v)!=fa[u]){
			fa[v]=u; dfs1(v); sz[u]+=sz[v];
		}
}
void dfs2(LL u){
	if (!top[u]) top[u]=u; LL t=0;
	dfn[u]=++clk; but[top[u]]=u;
	for (LL i=head[u],v;i;i=e[i].nxt)
		if ((v=e[i].v)!=fa[u] && sz[v]>sz[t]) t=v;
	if (!t){mdf(1,1,n,dfn[u],trans(0,INF)); return;} top[t]=top[u]; dfs2(t);
	for (LL i=head[u],v;i;i=e[i].nxt)
		if ((v=e[i].v)!=fa[u] && v!=t) dfs2(v);
}
void add(LL x,LL y){
	trans tmp2=qry(1,1,n,dfn[x],dfn[x]);
	trans tmp=trans(tmp2.a+y,qry(1,1,n,dfn[x],dfn[x]).b);
	while (x){
		if (fa[top[x]]){
			tmp2=qry(1,1,n,dfn[fa[top[x]]],dfn[fa[top[x]]]);
			tmp2.b-=qry(1,1,n,dfn[top[x]],dfn[but[top[x]]]).calc();
		}
		mdf(1,1,n,dfn[x],tmp);
		if (fa[top[x]]){
			tmp2.b+=qry(1,1,n,dfn[top[x]],dfn[but[top[x]]]).calc();
			tmp=tmp2;
		}
		x=fa[top[x]];
	}
}
int main(){
	scanf("%lld",&n);
	for (LL i=1;i<=n;i++) scanf("%lld",&c[i]);
	for (LL i=1;i<n;i++){
		scanf("%lld%lld",&x,&y);
		adde(x,y); adde(y,x);
	}
	dfs1(1); dfs2(1);
	for (LL i=1;i<=n;i++) add(i,c[i]);
	scanf("%lld",&m);
	while (m--){
		for (ch=getchar();ch!='Q' && ch!='C';ch=getchar());
		if (ch=='Q'){
			scanf("%lld",&x);
			printf("%lld\n",qry(1,1,n,dfn[x],dfn[but[top[x]]]).calc());
		}
		if (ch=='C'){
			scanf("%lld%lld",&x,&y);
			add(x,y);
		}
	}
	
	return 0;
}