首页 > 其他分享 >树上动态DP状态设计及实现细节

树上动态DP状态设计及实现细节

时间:2023-11-12 12:56:31浏览次数:31  
标签:mar int max son 细节 pmatrix 树上 DP

状态设计

由于具有更改操作,我们希望更改后会变的东西可以简单的通过线段树上单点修改来维护。

对于一般的常数层转移 DP,这一点较好处理。但是对于树上 DP,就需要结合重儿子进行设计另一个 \(g\) 数组,表示不含重儿子的 DP 值,就可以结合树剖快速计算。

这道,各点有不同代价,可覆盖子树所有叶节点,求覆盖子树所有叶节点的最小代价。

最先列的方程及转移矩阵:

\[f_u=\sum\min(f_v,a_v) \]

\[\begin{pmatrix} f_{son} & a_{son} \end{pmatrix} \begin{pmatrix} g_u & \infty \\ g_u & a_u-a_{son} \end{pmatrix} = \begin{pmatrix} f_{u} & a_{u} \end{pmatrix} \]

这是肯定不行的,因为改 \(a\) 值的时候会影响父亲,很麻烦。可以改变定义来规避这一点。

实现细节

  • 维护乘积的方向:横向量&逆向;列向量&正向

  • upd可以通过改g数组而不是传参

  • 本来不应使用叶子节点的转移矩阵,但是发现这与dp初值是一样的,可以减少码量

  • change的过程:
    算第一个g
    循环,当前upd,算下一个g
    最后一个upd

板子

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int N=1e5+10,M=2,inf=1e9;
int n,m,a[N],h[N],ne[N<<1],e[N<<1],idx,f[N][2],g[N][2],ed[N];
int dep[N],fa[N],size[N],son[N],top[N],num[N],cnt,be[N];
inline void add(int u,int v){
	ne[++idx]=h[u],h[u]=idx,e[idx]=v;
}
inline void dfs(int u,int fath){
	dep[u]=dep[fath]+1,fa[u]=fath,size[u]=1;
	f[u][1]=g[u][1]=a[u];
	for(int i=h[u],v;i;i=ne[i]){
		v=e[i];
		if(v!=fath){
			dfs(v,u);
			size[u]+=size[v];
			if(size[v]>size[son[u]]) son[u]=v,ed[u]=ed[v];
		}
	}
	for(int i=h[u],v;i;i=ne[i]){
		v=e[i];
		if(v!=fath){
			f[u][0]+=max(f[v][0],f[v][1]),f[u][1]+=f[v][0];
			if(v!=son[u]) g[u][0]+=max(f[v][0],f[v][1]),g[u][1]+=f[v][0];
		}
	}
	if(!son[u]) ed[u]=u;
}
inline void dfs1(int u,int gd){
	num[u]=++cnt,be[cnt]=u,top[u]=gd;
	if(son[u]) dfs1(son[u],gd);
	for(int i=h[u],v;i;i=ne[i]){
		v=e[i];
		if(v!=fa[u]&&v!=son[u]) dfs1(v,v);
	}
}
struct mar{
	int d[M][M];
};
inline mar operator*(mar a,mar b){
	mar c;
	c.d[0][0]=max(a.d[0][0]+b.d[0][0],a.d[0][1]+b.d[1][0]);
	c.d[0][1]=max(a.d[0][0]+b.d[0][1],a.d[0][1]+b.d[1][1]);
	c.d[1][0]=max(a.d[1][0]+b.d[0][0],a.d[1][1]+b.d[1][0]);
	c.d[1][1]=max(a.d[1][0]+b.d[0][1],a.d[1][1]+b.d[1][1]);
	return c;
}
struct node{
	int l,r;
	mar s;
}tr[N<<2];
inline void pushup(int u){
	tr[u].s=tr[u<<1|1].s*tr[u<<1].s;
}
inline void build(int u,int l,int r){
	tr[u]=/**/{l,r};
	if(l==r){
		tr[u].s=/**/{{{g[be[l]][0],g[be[l]][1]},{g[be[l]][0],-inf}}};
		return ;
	}
	int mid=l+r>>1;
	build(u<<1,l,mid),build(u<<1|1,mid+1,r);
	pushup(u);
}
inline void mdf(int u,int x){
	if(tr[u].l==tr[u].r){
		tr[u].s=/**/{{{g[be[x]][0],g[be[x]][1]},{g[be[x]][0],-inf}}};
		return ;
	}
	int mid=tr[u].l+tr[u].r>>1;
	if(x<=mid) mdf(u<<1,x);
	else mdf(u<<1|1,x);
	pushup(u);
}
inline mar query(int u,int l,int r){
	if(l<=tr[u].l&&tr[u].r<=r) return tr[u].s;
	int mid=tr[u].l+tr[u].r>>1;
	if(r<=mid) return query(u<<1,l,r);
	if(l>mid) return query(u<<1|1,l,r);
	return query(u<<1|1,l,r)*query(u<<1,l,r);
}
inline void change(int u,int x){
	g[u][1]+=x-a[u];
	mar la,nw;
	while(top[u]!=1){
		la=query(1,num[top[u]],num[ed[u]]);
		mdf(1,num[u]);
		nw=query(1,num[top[u]],num[ed[u]]);
		u=fa[top[u]];
		g[u][0]+=max(nw.d[0][0],nw.d[0][1])-max(la.d[0][0],la.d[0][1]);
		g[u][1]+=nw.d[0][0]-la.d[0][0];
	}
	mdf(1,num[u]);
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i) scanf("%d",&a[i]);
	for(int i=1,x,y;i<n;++i){
		scanf("%d%d",&x,&y);
		add(x,y),add(y,x);
	}
	dfs(1,0);
	dfs1(1,1);
	build(1,1,n);
	while(m--){
		int x,y;
		scanf("%d%d",&x,&y);
		change(x,y);
		a[x]=y;
		mar res=query(1,1,num[ed[1]]);
		printf("%d\n",max(res.d[0][0],res.d[0][1]));
	}
	return 0;
}

标签:mar,int,max,son,细节,pmatrix,树上,DP
From: https://www.cnblogs.com/mRXxy0o0/p/17827010.html

相关文章

  • 斜率优化DP
    使用场景状态\(O(n)\),转移\(O(n)\),只涉及\(i,j\)两个未知量,\(j\)的取值范围的左、右端单调,可以把\(f_i\)当做截距维护上(max)、下(min)凸包。需要注意的是,它作用不仅仅可以优化DP,本质是求某些最值,\(\color{red}\text{example}\)。也可以在\(\color{pink}\text{一些题}\)中求......
  • G - Cut and Reorder 状压DP
    我是题目链接首先显然先一操作,然后二操作这样不会影响最终结果一眼状压DP,选出一些a从前往后塞,f[i][j]表示选出的a状态为i,且结尾为j时最小花费转移就看上一个状态的结尾(设为k)和当前结尾(设为j)在a里的下标是否顺着挨着(就是j=k+1),不是顺着挨着就要加个c这样会tle#include<bits/std......
  • 【教3妹学编程-算法题】 在树上执行操作以后得到的最大分数
    3妹:2哥,今日都立冬了,可是天气一点都不冷。2哥 :立冬了,晚上要不要一起出去吃饺子?......
  • 【小沐学前端】Windows下搭建WordPress(二、相关工具安装)
    1、简介WordPress是基于PHP和MySQL的免费开源内容管理系统(CMS)。它是全球使用最广泛的CMS软件,截至2019年5月,它为排名前1000万个网站中提供了超过30%的支持,并拥有在使用CMS构建的所有网站中,估计有60%的市场份额。2、搭建环境2.1Nginx配置nginx.conf,文件在nginx目录下的conf文件夹......
  • DP做题记录
    蒟蒻DP太菜了QAQ。一点体会:DP就是如何通过最少的信息确定最优解。P5664[CSP-S2019]Emiya家今天的饭思考了一下,发现第3个要求很难直接搞,于是考虑正难则反,用总方案数减去不符合要求的方案数。求总方案数:\(g_{i,j}\)表示在前\(i\)行中选\(j\)个点的方案数,则\[g_{i,j}=g_......
  • P3842-DP【黄】
    想搜索到最后一层,就必得先完成前面层的搜索任务,这构成了对状态转移的启示,即当前层的DP值应该是此前层转移过来后得到的最佳值。但这道题看数据范围应该不能用二维数组,抱着侥幸的心理我使用了动态二维数组,dpij表示以第i层第j个为终点时的答案,结果MLE了,喜提42分,详见CODE-1。后来意......
  • CF1304E 1-Trees and Queries(lca+树上前缀和+奇偶性)
    题目二话不说,直接按题意模拟暴搜,当然\(O(nq)\)的复杂度显然是寄了的。不过,在模拟的过程中,我在链式前向星的删边中居然一开始错了,还是要mark一下以后注意。voiddel(intx,intpre){ e[top].to=e[top].next=0; h[x]=pre;//h[x]=0;<---tip}intmain(){ ......
  • 状态机模型DP
    //http://ybt.ssoier.cn:8088/problem_show.php?pid=1302#include<bits/stdc++.h>usingnamespacestd;constintN=2e5+10;intdp[N][3][3],n,w[N],t;intmain(){cin>>t;while(t--){cin>>n;intres=0;memset(......
  • [题解] AT_dp_w Intervals
    Intervals有\(m\)条形如\((l,r,a)\)的限制,表示如果\(s_{[l,r]}\)中有1就会有\(a\)的价值。你要求长度为\(n\)的01串的价值的最大值。\(n,m\le2\times10^5\)。将每个限制挂到右端点上,在右端点处计算贡献。然后我们就只关心最后一个1出现的位置了。......
  • 【小沐学前端】Windows下搭建WordPress(一、相关工具下载)
    1、简介WordPress是基于PHP和MySQL的免费开源内容管理系统(CMS)。它是全球使用最广泛的CMS软件,截至2019年5月,它为排名前1000万个网站中提供了超过30%的支持,并拥有在使用CMS构建的所有网站中,估计有60%的市场份额。1.1Nginxnginx[enginex]是一个HTTP和反向代理服务器,邮件代理......