洛谷P4338 [ZJOI2018]历史(LCT,树形DP,树链剖分)

时间:2022-05-05 19:30:01

洛谷题目传送门

ZJOI的考场上最弱外省选手T2 10分成功滚粗。。。。。。

首先要想到30分的结论

说实话Day1前几天刚刚刚掉了SDOI2017的树点涂色,考场上也想到了这一点

想到了又有什么用?反正想不到最大的贡献是怎么推出来的

然后晚上心中怀着九条CNM看完了Solution.pdf

貌似对我这个蒟蒻来说也只有这一题可做了。。。。。。

已知书上每个点access的总次数,构造出一个顺序,最大化虚实边的切换总次数

其实如果能发现最优顺序的构造是没有后效性的话,问题便可以进一步简化

考虑每个点的子树。假设已经对所有子树中的点构造出了一个最优顺序(一个序列),那么一定不会和它的所有祖先的子树中的最优序列产生冲突。这个并不好证明,仔细想一想应该能发现。

于是就可以单独考虑每个点\(x\)。能对\(x\)的实子边产生影响的是x的所有子树和\(x\)本身(access(x)会使\(x\)没有实子边),每切换一次都会使答案\(+1\)。显然同一个子树中产生的影响是相同的。于是我们要让来自不同子树(或\(x\)本身)尽可能交替access。当没有某个子树(或\(x\)本身)的\(a\)总和过大时,可以构造出使得(除了第一次)每一次access都有贡献的方案。如果某个子树(或\(x\)本身)的\(a\)总和过大,大于所有子树总和的一半时,是不可以的,那个子树(或\(x\)本身)的某几次操作肯定不会有贡献。用数学公式大概表示每个点的贡献为(\(S\)为子树的\(a\)之和,\(c\)为\(x\)的每个子树)

\[\min\{S_x-1,2*(S_x-\max\{a_x,\forall S_c\})\}
\]

当\(\max\{a_x,\forall S_c\}\gt {S_x+1\over2}\)时\(\min\)取后者

用树形DP算出来就有30分了

那么怎样快速修改呢?

首先,对某个点的\(a\)加上一个值\(w\),只可能会影响该点到根的路径上的点的贡献。

因为是加一个值,所以假如这些点中某些点的子树\(S\)大于它父亲子树\(S\)的一半,那么\(S_x+w\),\(\max\{a_x,\forall S_c\}\)也会\(+w\),带入上式发现贡献是不变的!

看到某个子树S大于所有子树总和的一半,有没有想到树剖?树剖的轻重边就是这样划分的啊!(反正我这种蒟蒻就是想不到)

同样对维护好每个点子树S的树进行轻重链剖分,某些点的子树a之和大于它父亲子树a之和的一半就连重边(否则连轻边),这样每个点至多有一个重儿子。类似树剖的证明,每个点到根的轻边总数(也就是我们可能会修改的点数)是\(\log\sum a\)级别的!

修改的复杂度也有保障啦!我们只要快速找到这些点就好了。用实链剖分维护子树信息即可(应该不能叫LCT吧,没有makeroot,link和cut,对于这个问题蒟蒻的LCT总结对LCT的概念也改了改,欢迎Julao们指正!)。全局保存ans,每次进行类access操作找到虚边,就让ans直接减去以前的贡献,加上w以后判断当前的情况决定是否要切换虚实边并让ans加上新的贡献即可。

为了方便计算以前的贡献,蒟蒻觉得可以保存一下以前贡献的类型(无非就三种,某子树过大、自己过大、都不是很大)算的时候就省去了一些判断的时间。

代码细节巨多,尤其是类access更新答案那部分。所以就算考场上想到了一些东西,我这种蒟蒻也未必写得出来吧!疯狂膜拜考场切T2的laofu爷Orzzzzzzzzzzzz!

#include<cstdio>
#define RG register
#define R RG int
#define I inline void
#define lc c[x][0]
#define rc c[x][1]
#define G ch=getchar()
typedef long long L;
const int N=400009,M=N<<1;
int f[N],c[N][2],he[N],ne[M],to[M];
L ans,a[N],si[N],s[N];
short tp[N];
bool r[N];
template<typename T>
I in(RG T&x){
RG char G;
while(ch<'-')G;
x=ch&15;G;
while(ch>'-')x*=10,x+=ch&15,G;
}
inline bool nroot(R x){
return c[f[x]][0]==x||c[f[x]][1]==x;
}
I up(R x){
s[x]=s[lc]+s[rc]+si[x]+a[x];
}
I rot(R x){
R y=f[x],z=f[y],k=c[y][1]==x,w=c[x][!k];
if(nroot(y))c[z][c[z][1]==y]=x;c[x][!k]=y;c[y][k]=w;
up(f[w]=y);f[y]=x;f[x]=z;
}
I splay(R x){
R y;
while(nroot(x)){
if(nroot(y=f[x]))
rot((c[f[y]][0]==y)^(c[y][0]==x)?x:y);
rot(x);
}
up(x);
}
void dp(R x){//dp预处理答案
R y,i,mp=x;
RG L mx=a[x];
for(i=he[x];i;i=ne[i]){
if(f[x]==(y=to[i]))continue;
f[y]=x;dp(y);
si[x]+=s[y];
if(mx<s[y])mx=s[y],mp=y;
}
if(mx<<1>(s[x]=si[x]+a[x])){
ans+=(s[x]-mx)<<1;
if(x!=mp)si[x]-=s[rc=mp];//子树过大
else tp[x]=1;//自己过大
}
else tp[x]=2,ans+=s[x]-1;//都不是很大
}
int main(){
R n,m,i,p=0,x,y;
RG L w,S;
in(n);in(m);
for(i=1;i<=n;++i)in(a[i]);
for(i=1;i<n;++i){
in(x);in(y);
to[++p]=y;ne[p]=he[x];he[x]=p;
to[++p]=x;ne[p]=he[y];he[y]=p;
}
dp(1);printf("%lld\n",ans);
while(m--){
in(x);in(w);
for(y=0;x;x=f[y=x]){
splay(x);
S=s[x]-s[lc];//算原来子树a总和,注意减s[lc]
ans-=tp[x]<2?(S-(tp[x]?a[x]:s[rc]))<<1:S-1;
S+=w;s[x]+=w;(y?si:a)[x]+=w;
if(s[y]<<1>S)si[x]+=s[rc],si[x]-=s[rc=y];//虚实切换
if(s[rc]<<1>S) tp[x]=0,ans+=(S-s[rc])<<1;//子树过大
else{
if(rc)si[x]+=s[rc],rc=0;//没有子树过大,一定变虚
if(a[x]<<1>S)tp[x]=1,ans+=(S-a[x])<<1;//自己过大
else tp[x]=2,ans+=S-1,rc=0;//都不是很大
}
}
printf("%lld\n",ans);
}
return 0;
}

洛谷P4338 [ZJOI2018]历史(LCT,树形DP,树链剖分)的更多相关文章

  1. P4338 &lbrack;ZJOI2018&rsqb;历史 LCT&plus;树形DP

    \(\color{#0066ff}{ 题目描述 }\) 这个世界有 n 个城市,这 n 个城市被恰好 \(n-1\) 条双向道路联通,即任意两个城市都可以 互相到达.同时城市 1 坐落在世界的中心,占 ...

  2. &lbrack;HDU 5293&rsqb;Tree chain problem&lpar;树形dp&plus;树链剖分&rpar;

    [HDU 5293]Tree chain problem(树形dp+树链剖分) 题面 在一棵树中,给出若干条链和链的权值,求选取不相交的链使得权值和最大. 分析 考虑树形dp,dp[x]表示以x为子树 ...

  3. ⌈洛谷1505&RightFloor;⌈BZOJ2157&RightFloor;⌈国家集训队&RightFloor;旅游【树链剖分】

    题目链接 [洛谷] [BZOJ] 题目描述 Ray 乐忠于旅游,这次他来到了T 城.T 城是一个水上城市,一共有 N 个景点,有些景点之间会用一座桥连接.为了方便游客到达每个景点但又为了节约成本,T ...

  4. 洛谷P3128 &lbrack;USACO15DEC&rsqb;最大流Max Flow &lbrack;树链剖分&rsqb;

    题目描述 Farmer John has installed a new system of  pipes to transport milk between the  stalls in his b ...

  5. 洛谷 P3258 &lbrack;JLOI2014&rsqb;松鼠的新家&lpar;树链剖分&rpar;

    题目描述松鼠的新家是一棵树,前几天刚刚装修了新家,新家有n个房间,并且有n-1根树枝连接,每个房间都可以相互到达,且俩个房间之间的路线都是唯一的.天哪,他居然真的住在”树“上. 松鼠想邀请小熊维尼前来 ...

  6. 洛谷 P3038 &lbrack;USACO11DEC&rsqb;牧草种植Grass Planting&lpar;树链剖分&rpar;

    题解:仍然是无脑树剖,要注意一下边权,然而这种没有初始边权的题目其实和点权也没什么区别了 代码如下: #include<cstdio> #include<vector> #in ...

  7. 洛谷 P2146 &lbrack;NOI2015&rsqb;软件包管理器 (树链剖分模板题)

    题目描述 Linux用户和OSX用户一定对软件包管理器不会陌生.通过软件包管理器,你可以通过一行命令安装某一个软件包,然后软件包管理器会帮助你从软件源下载软件包,同时自动解决所有的依赖(即下载安装这个 ...

  8. 洛谷 P3258 &lbrack;JLOI2014&rsqb;松鼠的新家 树链剖分&plus;差分前缀和优化

    目录 题面 题目链接 题目描述 输入输出格式 输入格式 输出格式 输入输出样例 输入样例: 输出样例: 说明 说明 思路 AC代码 优化 优化后AC代码 总结 题面 题目链接 P3258 [JLOI2 ...

  9. 洛谷P2146 &lbrack;NOI2015&rsqb;软件包管理器 题解 树链剖分&plus;线段树

    题目链接:https://www.luogu.org/problem/P2146 本题涉及算法: 树链剖分: 线段树(区间更新及求和,涉及懒惰标记) 然后对于每次 install x ,需要将 x 到 ...

随机推荐

  1. 用iframe设置代理解决ajax跨域请求问题

    面对ajax跨域请求的问题,想用代理的方式来解决这个跨域问题.在服务器端创建一个静态的代理页面,在客户端用iframe调用这个代理 今天在项目中需要做远程数据加载并渲染页面,直到开发阶段才意识到aja ...

  2. linux内核中sys&lowbar;poll&lpar;&rpar;的简化分析

    app:poll or select; kernel: sys_poll(); do_sys_poll(struct pollfd __user *ufds, unsigned int nfds,st ...

  3. javascript之String

    一.构造函数 new String(value) //构造函数 function String(value) //转换函数 二.属性 length 该字符串中的字符数 var str = new St ...

  4. 高级UNIX环境编程10 信号

    信号是软件中断,提供一种处理异步事件的方法 <signal.h> sigaction()

  5. 使用ThinkPHP&plus;Uploadify实现图片上传功能

    首先,将下载的Uploadify压缩包解压放到公共文件夹内.实现代码如下: 前台html部分: <script src="/uploadify/jquery.min.js" ...

  6. Android-往来&colon;添加到联系人

    //添加到联系人.使用事务 public void testAddContact() { String name[]={"周杰伦","谢霆锋","言承 ...

  7. JavaScript阻止事件冒泡(兼容IE、Chrome、FF)

    这里仅仅是一个简单代码demo,因为时间问题并未做深入研究,因为今天做项目时要用到阻止事件冒泡的内容,找了好多才找到一个可以使用的,特记录之. <!DOCTYPE HTML> <ht ...

  8. WordPress网站加速优化,一键免费使用七牛CDN插件

    利用wordpress搭建网站是个人建站的主流方案,我曾分享过wordpress网站加速优化必做的十件事,帮助了不少个人站长.今天介绍帮助wordpress网站提升速度至少10倍的免费CDN加速插件: ...

  9. 深入理解CSS盒模型

    如果你在面试的时候面试官让你谈谈对盒模型的理解,你是不是不知从何谈起.这种看似简单的题其实是最不好答的. 下面本文章将会从以下几个方面谈谈盒模型. 基本概念:标准模型 和IE模型 CSS如何设置这两种 ...

  10. 【java学习笔记】Properties

    Properties:可以持久化的映射,规定键和值的类型是String. Properties对象必须放到.properties文件中,其中properties文件默认为西欧编码,也因此不存储中文. ...