[bzoj 5210]最大连通子块和

news/2024/4/16 2:13:32

给出一棵n个点、以1为根的有根树,点有点权。要求支持如下两种操作:
M x y:将点x的点权改为y;
Q x:求以x为根的子树的最大连通子块和。
其中,一棵子树的最大连通子块和指的是:该子树所有子连通块的点权和中的最大值
(本题中子连通块包括空连通块,点权和为0)。

由于提高组2018考察了ddp,所以做了一道例题,顺便学习了一下。
这道题首先列出dp方程, f [ x ] = m a x ( 0 , Σ f [ y ] + w [ x ] ) f[x]=max(0,\Sigma f[y]+w[x]) f[x]=max(0,Σf[y]+w[x])(其中y是x的孩子)。这样我们就可以修改 Θ ( 1 ) \Theta(1) Θ(1),但询问 Θ ( x 的 子 树 大 小 ) \Theta(x的子树大小) Θ(x),会超时。
考虑链分治,令 g [ x ] = Σ f [ y ] + w [ x ] g[x]=\Sigma f[y]+w[x] g[x]=Σf[y]+w[x](其中y是x的轻孩子),那dp方程就转化成 f [ x ] = m a x ( 0 , f [ y ] + g [ x ] ) f[x]=max(0,f[y]+g[x]) f[x]=max(0,f[y]+g[x])(其中y是x的重孩子),那我们就可以发现这是求最大前缀和的形式。这样我们就可以解决以x为根的子树中包含x的最大连通子块和的查询,修改的话直接修改就可以了。
但问题是题目并不要求强制包含x,那么我们就还要记录一个值s,s[x]=max(f[x],s[y])(y为x的孩子)。从而我们发现询问的答案其实就为x到它所在的那条重链的底端的点的g的最大连续子段和,然后再和每个点的S-top(S-top为s[那个点的轻孩子]的max)取max就是了,那在线段树那里开多一个值ans来记录这个就可以了。那修改的时候,对于每个点要记录它的轻孩子的s值,方便修改,然后由于s[y]每次其实只有最大值有用,那可以对每一个点开一个可删堆。但由于我懒,所以我开了set。
那这道题就解决了,剩下就是一些实现上的细节。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<set>
using namespace std;
multiset<long long>s[200010];
inline int read()
{int x=0,f=1;char ch=getchar();while(ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0' && ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;
}
inline void write(long long x)
{if(x<0)putchar('-'),x=-x;if(x>9)write(x/10);putchar(x%10+'0');
}
struct node
{int x,y,next;
}a[400010];int len,last[200010];
inline void ins(int x,int y)
{len++;a[len].x=x;a[len].y=y;a[len].next=last[x];last[x]=len;
}
int fa[200010],son[200010],tot[200010];
inline void pre_tree_node(int x)
{tot[x]=1;for(int k=last[x];k;k=a[k].next){int y=a[k].y;if(y==fa[x])continue;fa[y]=x;pre_tree_node(y);tot[x]+=tot[y];if(tot[son[x]]<tot[y])son[x]=y;}
}
long long g[200010],w[200010],mx[200010];
int id,ys[200010],ex[200010],top[200010],dow[200010];
inline long long pre_tree_edge(int x,int tp)
{long long f;f=g[x]=w[x];top[x]=tp;ys[x]=++id;ex[id]=x;if(son[x]!=0)f+=pre_tree_edge(son[x],tp),dow[x]=dow[son[x]],mx[x]=mx[son[x]];else dow[x]=x;for(int k=last[x];k;k=a[k].next){int y=a[k].y;if(y==fa[x] || y==son[x])continue;long long ul=pre_tree_edge(y,y);g[x]+=ul;f+=ul;s[x].insert(mx[y]),mx[x]=max(mx[x],mx[y]);}long long wy=max(f,0LL);mx[x]=max(mx[x],wy);return wy;
}
struct trnode
{int l,r,lc,rc;long long sum,sl,sr,ans;//sumΪgµÄºÍ slΪgµÄ×î´óǰ׺ºÍ srΪgµÄ×î´óºó׺ºÍ
}tr[400010];int trlen;
inline trnode merge(trnode now,trnode lc,trnode rc)
{now.sum=lc.sum+rc.sum;now.sl=max(lc.sl,lc.sum+rc.sl);now.sr=max(rc.sr,rc.sum+lc.sr);now.ans=max(max(lc.ans,rc.ans),lc.sr+rc.sl);return now;
}
inline void bt(int l,int r)
{trlen++;int now=trlen;tr[now].l=l;tr[now].r=r;if(l==r){tr[now].sum=g[ex[l]],tr[now].sl=tr[now].sr=max(0LL,g[ex[l]]);long long wy=0;if(!s[ex[l]].empty())wy=*s[ex[l]].rbegin();tr[now].ans=max(g[ex[l]],wy);}else{int mid=(l+r)>>1;tr[now].lc=trlen+1;bt(l,mid);tr[now].rc=trlen+1;bt(mid+1,r);tr[now]=merge(tr[now],tr[tr[now].lc],tr[tr[now].rc]);}
}
inline void change(int now,int x)
{if(tr[now].l==tr[now].r){tr[now].sum=g[ex[x]],tr[now].sl=tr[now].sr=max(0LL,g[ex[x]]);long long wy=0;if(!s[ex[x]].empty())wy=*s[ex[x]].rbegin();tr[now].ans=max(g[ex[x]],wy);return ;}int lc=tr[now].lc,rc=tr[now].rc,mid=(tr[now].l+tr[now].r)>>1;if(x<=mid)change(lc,x);else change(rc,x);tr[now]=merge(tr[now],tr[lc],tr[rc]);
}
inline trnode getans(int now,int l,int r)
{if(tr[now].l==l && tr[now].r==r)return tr[now];int lc=tr[now].lc,rc=tr[now].rc,mid=(tr[now].l+tr[now].r)>>1;if(r<=mid)return getans(lc,l,r);else if(mid+1<=l)return getans(rc,l,r);else return merge(tr[0],getans(lc,l,mid),getans(rc,mid+1,r));
}
inline void solve(int x)
{while(x){int tp=top[x],dw=dow[x],f=fa[tp];trnode ul=getans(1,ys[tp],ys[dw]);s[f].erase(ul.ans),g[f]-=ul.sl;change(1,ys[x]);ul=getans(1,ys[tp],ys[dw]);s[f].insert(ul.ans),g[f]+=ul.sl;x=f;}
}
char ss[2];
int main()
{//freopen("a.in","r",stdin);//freopen("a.out","w",stdout);int n=read(),m=read();for(int i=1;i<=n;i++)w[i]=read();for(int i=1;i<n;i++){int x=read(),y=read();ins(x,y),ins(y,x);}pre_tree_node(1),pre_tree_edge(1,1);bt(1,n);while(m--){scanf("%s",ss+1);int x=read();if(ss[1]=='Q')write(getans(1,ys[x],ys[dow[x]]).ans),puts("");else{int y=read();g[x]+=y-w[x];solve(x);w[x]=y;}}return 0;
}

http://www.ppmy.cn/news/303291.html

相关文章

SQL Server 附加数据库 错误5210

前言 那天在弄机房的时候,附加数据库总是附加不上,然而将附加数据库文件放到优盘里,就可以附加成功。我也不知道为什么了,但是这次还是别将就了。于是乎,上网查了查原来是权限不够啊。这可怎么办,见下面三种方法: 【方法一】 设置mdf文件夹下的权限,在文件夹上右击…

bzoj5210: 最大连通子块和

传送门 这题一看就是动态dp&#xff0c;先考虑暴力 s表示不选这个点&#xff0c;f表示选这个点 s [ i ] max ⁡ ( s [ t ] , f [ t ] ) s[i] \max(s[t], f[t]) s[i]max(s[t],f[t]) f [ i ] max ⁡ ( 0 , V x ∑ f [ t ] ) f[i] \max(0, V_x \sum f[t]) f[i]max(0,Vx​∑…

Capstone CS5210 datasheet|Capstone CS5210规格书|低成本HDMI转VGA方案设计

Capstone最新推出的一款HDMI转VGA音视频转接线或者转换器方案芯片CS5210。 其设计的优势在于内置晶振&#xff0c;外围电路器件较少设计简单&#xff0c;芯片封装集成度较高&#xff0c;方案BOM成本低&#xff0c;相比其他方案产品更具性价比&#xff0c;下面将着重讲述CS5210…

bzoj5210最大连通子块和

题解&#xff1a; 考虑朴素的dp:$$f_{u} max(\sum_{v} f_{v} w_{u} , 0) \ \ \ \ h_{u} max( max_{v} \{ h_{v} \} , h_{u} )$$考虑利用树剖修改&#xff1a;记$son_{u}$为$u$的重儿子&#xff0c;$g_{u}$为$u$所有轻儿子之和加$w_{u}$&#xff1b;方程变成&#xff1a;$g…

Capstone CS5210|CS5210 HDMI to VGA转换器

1&#xff1a;视频输入接口——HDMI HDMI输入格:720P,1080I, 1080P 2&#xff1a;视频输出接口——VGA VGA输出分辨率:随输入的HDMI信号而变化 3: 支持分辨率&#xff1a;800*600, 1024*768, 1280*720,1280*1024,1920*1080 此款HDMI转VGA转换器&#xff0c;其输出VGA信号可送…

CS5210的参数详情资料分享

CS5210概述 Capstone CS5210 HDMI到VGA转换器结合了HDMI输入接口和模拟RGB DAC输出。支持内部LDO&#xff0c;节省成本&#xff0c;优化电路板空间。嵌入式单片机基于工业标准8051内核。 CS5210适用于各种市场系统和显示应用程序&#xff0c;如笔记本电脑、主板、台式机、转换和…

Capstone/CS5210芯片|CS5210设计方案|CS5210设计资料

1 CS5210简介 Capstone CS5210 HDMI到VGA转换器结合了HDMI输入接口和模拟RGB DAC输出。支持内部LDO&#xff0c;节省成本&#xff0c;优化电路板空间。嵌入式单片机基于工业标准8051内核。 CS5210适用于各种市场系统和显示应用程序&#xff0c;如笔记本电脑、主板、台式机、转…

移除联想M5210阵列卡(3650M5)的缓存模块以开启JBOD模式

由于只有不配备缓存阵列卡才支持JBOD / 硬盘直通模式功能&#xff0c;如需在配有缓存模块的ServerRAID M5210阵列卡上使用JBOD模式&#xff0c;必须手动拆除缓存模块。 本例是在配有ServerRAID M5210的System x3550 M5服务器上实施拆除缓存模块的操作&#xff0c;其他机型也可以…

hdu 5210 Delete

原题链接&#xff1a;http://acm.hdu.edu.cn/showproblem.php?pid5210 简单题如下&#xff1a; 1 #include<algorithm>2 #include<iostream>3 #include<cstdlib>4 #include<cstdio>5 using std::sort;6 const int Max_N 1010;7 int arr[Max_N];8 int…

华为OceanStor 5210 V5存储重置管理员密码

连接管理网口至网络 原文链接 背景信息 每个控制器上都设置有一个管理网口和维护网口。维护网口用于紧急情况下的特殊维护&#xff0c;因此一般只使用管理网口来进行配置管理。管理网口与维护终端之间能够正常通信&#xff08;管理网口与维护终端在同一网段或管理网口与维护…

Capstone CS5210规格书|低成本HDMI转VGA方案设计

Capstone最新推出的一款HDMI转VGA音视频转接线或者转换器方案芯片CS5210。 其设计的优势在于内置晶振&#xff0c;外围电路器件较少设计简单&#xff0c;芯片封装集成度较高&#xff0c;方案BOM成本低&#xff0c;相比其他方案产品更具性价比&#xff0c;下面将着重讲述CS5210…

m5210阵列卡 linux驱动下载,IBM M5210阵列卡驱动下载|IBM阵列卡m5210 2008R2驱动 - 驱动无忧...

联想IBM m5210服务器阵列卡支持WIN2008R2系统下的驱动程序。 具体支持以下系统&#xff1a; srv_2003_x64 srv_2003_x86 srv_2008_x64 srv_2008_x86 vista_x64 vista_x86 win8.1_x64 win8.1_x86 win8_x64 win8_x86 xp_x64 驱动文件&#xff1a; driverconfigparam(1).def drive…

一文看懂:BTS5210G 智能高侧电源开关

BTS5210G&#xff0c;英飞凌&#xff08;Infineon&#xff09;国际品牌制造&#xff0c;双通道2x140mΩ&#xff0c;工作电压5.5V-40V&#xff0c;一款需求极大的智能高侧电源开关。很多人可能不太了解BTS5210G&#xff0c;接下来&#xff0c;供应商东沃电子要科普的是BTS5210G…

台湾安格AG6202与CS5210参数差异与区别|HDMI转VGA方案比较|AG6202与CS5210电路设计差异

台湾安格AG6202与台湾瑞奇达CS5210参数差异与区别|HDMI转VGA方案比较|AG6202与CS5210电路设计差异 台湾安格AG6202与CS5210都是用于设计HDMI转VGA不带音频输出的芯片方案。 台湾安格AG6202与CS5210芯片概述 AG6200芯片是一个HDMI&#xff08;高清多媒体接口&#xff09;到VG…

用结构体实现程序设计:找出分数最高的学生,并显示其基本信息(学生信息管理,简易版)

提示&#xff1a;可以复制&#xff0c;来源于大学测试题 文章目录 一、结构体二、使用步骤 1.源代码2.测试总结 提示&#xff1a;以下是本篇文章正文内容 一、结构体 1.运用结构概念 2.结合数组&#xff0c;将数据存入数组内 3.找出最高的分数 并打印相关学生信息 4.成绩…

关于三进制

在写代码的时候&#xff0c;用到位运算&#xff0c;其中网上有人解法中的二进制模拟三进制的字眼吸引住了我。 百度之&#xff0c;在茫茫网页中发现了知乎中关于”三进制优于二进制的讨论“&#xff0c;好奇的点进去一看&#xff0c;还挺有道理的&#xff0c;确切的说应该是对…

vue大屏展示 代码 从0 到1

1、基本骨架 2、填充内容 3、G2图 4、大屏数据展示组件库DataV 官网 1、基本骨架 <template><div id"parentDiv"><myHeader></myHeader><div id"container" class"flex-a-center-j-between"><div class"…

JSP省市区三级联动下拉选

JSPJqueryOracle实现省市区三级联动下拉选菜单 自己搞了一下午,刚开始觉得还有点麻烦,不过搞过一遍之后就觉得简单了,供大家互相学习,具体代码如下: 1.jsp页面代码&#xff1a; </pre><pre name"code" class"html"><tr><td>所在…
最新文章