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. 源码包…...

Linux应用开发之网络套接字编程(实例篇)
服务端与客户端单连接 服务端代码 #include <sys/socket.h> #include <sys/types.h> #include <netinet/in.h> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <arpa/inet.h> #include <pthread.h> …...

【OSG学习笔记】Day 18: 碰撞检测与物理交互
物理引擎(Physics Engine) 物理引擎 是一种通过计算机模拟物理规律(如力学、碰撞、重力、流体动力学等)的软件工具或库。 它的核心目标是在虚拟环境中逼真地模拟物体的运动和交互,广泛应用于 游戏开发、动画制作、虚…...
React hook之useRef
React useRef 详解 useRef 是 React 提供的一个 Hook,用于在函数组件中创建可变的引用对象。它在 React 开发中有多种重要用途,下面我将全面详细地介绍它的特性和用法。 基本概念 1. 创建 ref const refContainer useRef(initialValue);initialValu…...
python报错No module named ‘tensorflow.keras‘
是由于不同版本的tensorflow下的keras所在的路径不同,结合所安装的tensorflow的目录结构修改from语句即可。 原语句: from tensorflow.keras.layers import Conv1D, MaxPooling1D, LSTM, Dense 修改后: from tensorflow.python.keras.lay…...
IP如何挑?2025年海外专线IP如何购买?
你花了时间和预算买了IP,结果IP质量不佳,项目效率低下不说,还可能带来莫名的网络问题,是不是太闹心了?尤其是在面对海外专线IP时,到底怎么才能买到适合自己的呢?所以,挑IP绝对是个技…...

【Linux系统】Linux环境变量:系统配置的隐形指挥官
。# Linux系列 文章目录 前言一、环境变量的概念二、常见的环境变量三、环境变量特点及其相关指令3.1 环境变量的全局性3.2、环境变量的生命周期 四、环境变量的组织方式五、C语言对环境变量的操作5.1 设置环境变量:setenv5.2 删除环境变量:unsetenv5.3 遍历所有环境…...

什么是VR全景技术
VR全景技术,全称为虚拟现实全景技术,是通过计算机图像模拟生成三维空间中的虚拟世界,使用户能够在该虚拟世界中进行全方位、无死角的观察和交互的技术。VR全景技术模拟人在真实空间中的视觉体验,结合图文、3D、音视频等多媒体元素…...

Xela矩阵三轴触觉传感器的工作原理解析与应用场景
Xela矩阵三轴触觉传感器通过先进技术模拟人类触觉感知,帮助设备实现精确的力测量与位移监测。其核心功能基于磁性三维力测量与空间位移测量,能够捕捉多维触觉信息。该传感器的设计不仅提升了触觉感知的精度,还为机器人、医疗设备和制造业的智…...

Axure 下拉框联动
实现选省、选完省之后选对应省份下的市区...

聚六亚甲基单胍盐酸盐市场深度解析:现状、挑战与机遇
根据 QYResearch 发布的市场报告显示,全球市场规模预计在 2031 年达到 9848 万美元,2025 - 2031 年期间年复合增长率(CAGR)为 3.7%。在竞争格局上,市场集中度较高,2024 年全球前十强厂商占据约 74.0% 的市场…...