2021牛客OI赛前集训营-提高组(第四场) T3快速访问
2021牛客OI赛前集训营-提高组(第四场)
题目大意
有一棵n+1n+1n+1个节点的树,根节点为0。给你一个kkk,定义集合Si={j∈Z∣max(1,i−k)≤j<i}∪{0}S_i=\{j\in Z|\max(1,i-k)\leq j<i\}\cup\{0\}Si={j∈Z∣max(1,i−k)≤j<i}∪{0}。
Ai=∑j∈Sidis(i,j)2A_i=\sum\limits_{j\in S_i}dis(i,j)^2Ai=j∈Si∑dis(i,j)2,dis(i,j)dis(i,j)dis(i,j)指iii到jjj在树上的距离。求A1,A2,…,AnA_1,A_2,\dots,A_nA1,A2,…,An分别是多少。
题解
令aia_iai表示iii在树上的深度,注意根节点的深度为1。
那么dis(i,j)2=(ai+aj−2alca)2=ai2+aj2+2aiaj−4alcaai−4alcaaj+4alca2dis(i,j)^2=(a_i+a_j-2a_{lca})^2=a_i^2+a_j^2+2a_ia_j-4a_{lca}a_i-4a_{lca}a_j+4a_{lca}^2dis(i,j)2=(ai+aj−2alca)2=ai2+aj2+2aiaj−4alcaai−4alcaaj+4alca2
我们可以枚举iii,用树链剖分来维护jjj的值。
对于ai2a_i^2ai2,可以直接得出。
对于aj2a_j^2aj2,将所有在SiS_iSi中的jjj求前缀和即可。
对于2aiaj2a_ia_j2aiaj,对aja_jaj求前缀和,再乘上2ai2a_i2ai。
对于4alcaai4a_{lca}a_i4alcaai,对每个SiS_iSi中的jjj,都将jjj到根节点的路径上的点加1,然后查询iii到根节点的路径上的对应值的和,再乘上4ai4a_i4ai即可。
对于4alcaaj4a_{lca}a_j4alcaaj,对每个SiS_iSi中的jjj,都将jjj到根节点的路径上的点加aja_jaj,然后查询iii到根节点的路径上的对应值的和,再乘上444即可。
对于4alca24a_{lca}^24alca2,对每个SiS_iSi中的jjj,都将jjj到根节点的路径上的点加ak∗2−1a_k*2-1ak∗2−1(kkk表示当前节点),然后查询iii到根节点的路径上的对应值的和,因为x2=1+3+5+⋯+(x∗2−1)x^2=1+3+5+\cdots+(x*2-1)x2=1+3+5+⋯+(x∗2−1),所以这样求出的就是alca2a_{lca}^2alca2,然后乘444即可。
对于jjj进入集合或离开集合,在jjj到根节点的路径上进行区间修改即可。
为什么根节点的深度为1而不为0呢?因为只有根节点的深度为1,那么每个点到根节点的路径的长度才能等于这个点的深度,这样才能更好地实现。
时间复杂度为O(nlog2n)O(n\log^2 n)O(nlog2n)。
code
#include<bits/stdc++.h>
#define lc k<<1
#define rc k<<1|1
using namespace std;
int n,k,x,y,tot=0,d[500005],l[500005],r[500005],dep[500005],fa[500005],siz[500005],son[500005];
int tp[200005],s[200005],re[200005];
long long ans,hv1[800005],hv2[800005],mx1[800005],mx2[800005],mx3[800005],ly1[800005],ly2[800005],ly3[800005];
void add(int xx,int yy){l[++tot]=r[xx];d[tot]=yy;r[xx]=tot;
}
void dfs1(int u,int f){fa[u]=f;dep[u]=dep[f]+1;siz[u]=1;for(int i=r[u];i;i=l[i]){if(d[i]==f) continue;dfs1(d[i],u);siz[u]+=siz[d[i]];if(siz[d[i]]>siz[son[u]]) son[u]=d[i];}
}
void dfs2(int u,int f){if(son[u]){tp[son[u]]=tp[u];s[son[u]]=++s[0];re[s[0]]=son[u];dfs2(son[u],u);}for(int i=r[u];i;i=l[i]){if(d[i]==f||d[i]==son[u]) continue;tp[d[i]]=d[i];s[d[i]]=++s[0];re[s[0]]=d[i];dfs2(d[i],u);}
}
void build(int k,int l,int r){if(l==r){hv1[k]=2ll*dep[re[l]]-1;hv2[k]=1ll;return;}int mid=l+r>>1;build(lc,l,mid);build(rc,mid+1,r);hv1[k]=hv1[lc]+hv1[rc];hv2[k]=hv2[lc]+hv2[rc];
}
void down(int k){mx1[lc]+=ly1[k]*hv1[lc];ly1[lc]+=ly1[k];mx2[lc]+=ly2[k]*hv2[lc];ly2[lc]+=ly2[k];mx3[lc]+=ly3[k]*hv2[lc];ly3[lc]+=ly3[k];mx1[rc]+=ly1[k]*hv1[rc];ly1[rc]+=ly1[k];mx2[rc]+=ly2[k]*hv2[rc];ly2[rc]+=ly2[k];mx3[rc]+=ly3[k]*hv2[rc];ly3[rc]+=ly3[k];ly1[k]=ly2[k]=ly3[k]=0;
}
void ch(int k,int l,int r,int x,int y,long long t,int u){if(l>=x&&r<=y){mx1[k]+=t*hv1[k];ly1[k]+=t;mx2[k]+=t*hv2[k];ly2[k]+=t;mx3[k]+=t*dep[u]*hv2[k];ly3[k]+=t*dep[u];return;}if(l>y||r<x) return;if(l==r) return;if(ly1[k]||ly2[k]||ly3[k]) down(k);int mid=l+r>>1;if(x<=mid) ch(lc,l,mid,x,y,t,u);if(y>mid) ch(rc,mid+1,r,x,y,t,u);mx1[k]=mx1[lc]+mx1[rc];mx2[k]=mx2[lc]+mx2[rc];mx3[k]=mx3[lc]+mx3[rc];
}
void find(int k,int l,int r,int x,int y,int u){if(l>=x&&r<=y){ans+=4ll*(mx1[k]-mx2[k]*dep[u]-mx3[k]);return;}if(l>y||r<x) return;if(l==r) return;if(ly1[k]||ly2[k]||ly3[k]) down(k);int mid=l+r>>1;if(x<=mid) find(lc,l,mid,x,y,u);if(y>mid) find(rc,mid+1,r,x,y,u);
}
void ask(int i){int t=i;while(i>=1){find(1,1,s[0],s[tp[i]],s[i],t);i=fa[tp[i]];}
}
void ins(int i){int t=i;while(i>=1){ch(1,1,s[0],s[tp[i]],s[i],1,t);i=fa[tp[i]];}
}
void del(int i){int t=i;while(i>=1){ch(1,1,s[0],s[tp[i]],s[i],-1,t);i=fa[tp[i]];}
}
int main()
{scanf("%d%d",&n,&k);++n;for(int i=1;i<n;i++){scanf("%d%d",&x,&y);++x;++y;add(x,y);add(y,x);}dfs1(1,0);s[1]=++s[0];re[s[0]]=1;tp[1]=1;dfs2(1,0);build(1,1,s[0]);long long sum1=0,sum2=0;for(int i=2,vt,vk=2;i<=n;i++){vt=max(2,i-k);while(vk<vt){sum1-=1ll*dep[vk]*dep[vk];sum2-=1ll*dep[vk];del(vk);++vk;}ans=1ll*(dep[i]-1)*(dep[i]-1)+1ll*(i-vt)*dep[i]*dep[i]+sum1+2ll*dep[i]*sum2;ask(i);printf("%lld\n",ans);sum1+=1ll*dep[i]*dep[i];sum2+=1ll*dep[i];ins(i);}return 0;
}
相关文章:
2021牛客OI赛前集训营-提高组(第四场) T3快速访问
2021牛客OI赛前集训营-提高组(第四场) 题目大意 有一棵n1n1n1个节点的树,根节点为0。给你一个kkk,定义集合Si{j∈Z∣max(1,i−k)≤j<i}∪{0}S_i\{j\in Z|\max(1,i-k)\leq j<i\}\cup\{0\}Si{j∈Z∣max(1,i−k)≤j<i…...

【大数据是什么】
大数据是什么大数据是做什么的?大数据主要有哪些职位 ?大数据运维工程师数据仓库开发工程师ETL工程师大数据开发工程师BI工程师算法工程师大数据平台开发工程师大数据架构师讲述一下自己的大数据学习之路大数据是做什么的? 2014年,…...

大数据 | centos7图形界面无法执行yum命令
大家好,今天是三八女神节了! 你知道吗?世界上第一位电脑程序设计师是名女性,Ada Lovelace (1815-1852)。 她是一位英国数学家兼作家,第一位主张计算机不只可以用来算数的人,也发表了第一段分析机用的演算…...

三维人脸实践:基于Face3D的渲染、生成与重构 <一>
face3d: Python tools for processing 3D face git code: https://github.com/yfeng95/face3d paper list: PaperWithCode 该方法广泛用于基于三维人脸关键点的人脸生成、属性检测(如位姿、深度、PNCC等),能够快速实现人脸建模与渲染。推荐…...
Javascript 设计模式
设计模式的五大设计原则(SOLID)单一职责:一个程序只需要做好一件事。如果功能过于复杂就拆分开,保证每个部分的独立开放封闭原则:对扩展开放,对修改封闭。增加需求时,扩展新代码,而不是修改源代码。这是软件设计的终极…...

JAVA-文档工具screw-gui
前言 为什么萌生了写文档工具得想法,因为在项目开发得过程中,经常需要补充一些文档,比如数据库文档、详细设计文档等等,文档与项目相绑定,在项目需求新增或变更时,文档也需要反反复复得修改。 1. 数据库…...

开源鸿蒙南向嵌入学习笔记——NAPI框架学习(一)
开源鸿蒙南向嵌入学习笔记——NAPI框架学习(一) 前言——系列介绍 本系列文章主要是记录笔者在鸿蒙南向的学习与工作中的知识点笔记记录,其中不止会针对鸿蒙中的学习问题进行思考与记录,也会对涉及到的一些嵌入式等其他领域知识&…...

Spring - Spring框架概述面试题总结
文章目录01. 什么是Spring?02. Spring框架的设计目标,设计理念,和核心是什么?03. Spring的优点是什么?04. Spring框架中都用到了哪些设计模式?05. Spring有哪些应用场景?06. Spring由哪些模块组成…...
学习python好就业么
Python的普及与数据挖掘、人工智能和数值计算等领域的蓬勃发展相关,但同时也与普遍编程需求的增加有关。 Python作为人工智能的头号语言,一方面会吸引大量计划从事人工智能的人来学习,另一方面自然也带动了网络上对这门“新语言”的关注和讨…...
瑞幸咖啡的最终目标并不是做国内市场大哥
出品 | 何玺 排版 | 叶媛 日前,瑞幸咖啡发布2022年第四季度及全年财报。数据显示,在刚刚过去的2022年,瑞幸咖啡首次实现了营收超百亿,门店规模也超越老对手星巴克,成为了国内第一连锁咖啡品牌。 那么,瑞幸…...
GPT 模型介绍 | GPT3 / GPT3.5 + Flask | Github源码链接
1. 模型介绍 Chatgpt 使用与 InstructGPT相同的方法,使用来自人类反馈的强化学习 (RLHF) 来训练该模型,但数据收集设置略有不同。我们使用监督微调训练了一个初始模型:人类 AI 训练员提供对话,他们在对话中扮演双方——用户和 AI…...

蓝桥杯入门即劝退(二十六)组合问题(回溯算法)
-----持续更新Spring入门系列文章----- 如果你也喜欢Java和算法,欢迎订阅专栏共同学习交流! 你的点赞、关注、评论、是我创作的动力! -------希望我的文章对你有所帮助-------- 专栏:蓝桥杯系列 一、题目描述 给定两个整数 n …...

现代卷积神经网络(ResNet)
专栏:神经网络复现目录 本章介绍的是现代神经网络的结构和复现,包括深度卷积神经网络(AlexNet),VGG,NiN,GoogleNet,残差网络(ResNet),稠密连接网络…...
PTA:L1-019 谁先倒、L1-020 帅到没朋友、L1-021 重要的话说三遍(C++)
目录 L1-019 谁先倒 问题描述: L1-020 帅到没朋友 问题描述: 实现代码(只过了部分): L1-021 重要的话说三遍 问题描述: 实现代码: 无解析 L1-019 谁先倒 问题描述: 划拳是…...
STL常见容器之set/multiset、map/multimap
set/multiset—集合容器 特点 所有元素都会在插入时自动被排序 本质 set/multiset属于关联式容器,底层结构是二叉树实现 set和multiset区别 set不可以插入重复数据,而multiset可以set插入数据的同时会返回插入结果,表示插入是否成功multiset…...
ThreadLocal 实现原理
每个 Thread 中都存储着一个成员变量:ThreadLocalMap /** InheritableThreadLocal values pertaining to this thread. This map is* maintained by the InheritableThreadLocal class.*/ThreadLocal.ThreadLocalMap inheritableThreadLocals null; ThreadLocal 本…...

BUUCTF [羊城杯 2020]easyre 题解
一.查壳 64位无壳 二.主函数逻辑 可以得知flag长度为38,然后进行三次加密 第一次加密是base64加密,得到code1 第二次加密是将code1拆成四段赋给code2 第三次加密是将code2内的数字和字母移3位,其他字符不变 str2保存的是最终的加密字符 三.encode_one_base64 看到主函数…...

网络协议(十二):HTTPS(SSL/TLS、TLS1.2的连接)
网络协议系列文章 网络协议(一):基本概念、计算机之间的连接方式 网络协议(二):MAC地址、IP地址、子网掩码、子网和超网 网络协议(三):路由器原理及数据包传输过程 网络协议(四):网络分类、ISP、上网方式、公网私网、NAT 网络…...
九九乘法表--课后程序(Python程序开发案例教程-黑马程序员编著-第3章-课后作业)
实例9:九九乘法表 乘法口诀是中国古代筹算中进行乘法、除法、开方等运算的基本计算规则,沿用至今已有两千多年。古代的乘法口诀与现在使用的乘法口诀顺序相反,自上而下从“九九八十一”开始到“一一如一”为止,因此,古…...

在超算上安装文件树命令tree
超算平台使用的centos系统没有内置tree命令,需要通过源码安装。记录安装流程如下。 1. 下载源码包 下载链接如下: http://mama.indstate.edu/users/ice/tree/ 选择“Download the latest version” 如本文下载了源码包“tree-2.1.0.tgz”. 2. 源码包…...

VB.net复制Ntag213卡写入UID
本示例使用的发卡器:https://item.taobao.com/item.htm?ftt&id615391857885 一、读取旧Ntag卡的UID和数据 Private Sub Button15_Click(sender As Object, e As EventArgs) Handles Button15.Click轻松读卡技术支持:网站:Dim i, j As IntegerDim cardidhex, …...

深入浅出深度学习基础:从感知机到全连接神经网络的核心原理与应用
文章目录 前言一、感知机 (Perceptron)1.1 基础介绍1.1.1 感知机是什么?1.1.2 感知机的工作原理 1.2 感知机的简单应用:基本逻辑门1.2.1 逻辑与 (Logic AND)1.2.2 逻辑或 (Logic OR)1.2.3 逻辑与非 (Logic NAND) 1.3 感知机的实现1.3.1 简单实现 (基于阈…...
现有的 Redis 分布式锁库(如 Redisson)提供了哪些便利?
现有的 Redis 分布式锁库(如 Redisson)相比于开发者自己基于 Redis 命令(如 SETNX, EXPIRE, DEL)手动实现分布式锁,提供了巨大的便利性和健壮性。主要体现在以下几个方面: 原子性保证 (Atomicity)ÿ…...

在Mathematica中实现Newton-Raphson迭代的收敛时间算法(一般三次多项式)
考察一般的三次多项式,以r为参数: p[z_, r_] : z^3 (r - 1) z - r; roots[r_] : z /. Solve[p[z, r] 0, z]; 此多项式的根为: 尽管看起来这个多项式是特殊的,其实一般的三次多项式都是可以通过线性变换化为这个形式…...

通过MicroSip配置自己的freeswitch服务器进行调试记录
之前用docker安装的freeswitch的,启动是正常的, 但用下面的Microsip连接不上 主要原因有可能一下几个 1、通过下面命令可以看 [rootlocalhost default]# docker exec -it freeswitch fs_cli -x "sofia status profile internal"Name …...

stm32wle5 lpuart DMA数据不接收
配置波特率9600时,需要使用外部低速晶振...
0x-3-Oracle 23 ai-sqlcl 25.1 集成安装-配置和优化
是不是受够了安装了oracle database之后sqlplus的简陋,无法删除无法上下翻页的苦恼。 可以安装readline和rlwrap插件的话,配置.bahs_profile后也能解决上下翻页这些,但是很多生产环境无法安装rpm包。 oracle提供了sqlcl免费许可,…...

Java中HashMap底层原理深度解析:从数据结构到红黑树优化
一、HashMap概述与核心特性 HashMap作为Java集合框架中最常用的数据结构之一,是基于哈希表的Map接口非同步实现。它允许使用null键和null值(但只能有一个null键),并且不保证映射顺序的恒久不变。与Hashtable相比,Hash…...
6.9本日总结
一、英语 复习默写list11list18,订正07年第3篇阅读 二、数学 学习线代第一讲,写15讲课后题 三、408 学习计组第二章,写计组习题 四、总结 明天结束线代第一章和计组第二章 五、明日计划 英语:复习l默写sit12list17&#…...
Linux中INADDR_ANY详解
在Linux网络编程中,INADDR_ANY 是一个特殊的IPv4地址常量(定义在 <netinet/in.h> 头文件中),用于表示绑定到所有可用网络接口的地址。它是服务器程序中的常见用法,允许套接字监听所有本地IP地址上的连接请求。 关…...