首页 > 其他分享 >P3233 [HNOI2014] 世界树

P3233 [HNOI2014] 世界树

时间:2023-11-01 09:12:59浏览次数:31  
标签:结点 子树内 HNOI2014 世界 P3233 管辖 关键点

将关键点以深度为第一关键字,编号为第二关键字从小到大排序。

建完虚树后依次考虑这些关键点可能的管辖的结点。每次在虚树上向上跳,当遇到某个已经被访问过的结点时,根据我们的排序条件,显然再往上的结点就一定不是当前关键点管辖的了。但是在向上跳的这条链上的子树内的结点不一定由当前关键点管辖,也有可能由管辖上面那个访问过的结点的关键点管辖,具体分界点可以用两个关键点的距离计算出来。

确定当前关键点可能的管辖的结点后,容易发现它们一定是某棵子树内的所有结点。其中在向上跳的那条链上也就是访问过的那些结点一定不会变了,但它们子树内的结点可能由后面的关键点管辖。我们不妨先将当前关键点的答案置为子树大小,然后在后面遇到新的在子树内的关键点时,减去它们的子树大小即可。

这个方法非常简洁好写,让这题成为了一道有趣的题!

标签:结点,子树内,HNOI2014,世界,P3233,管辖,关键点
From: https://www.cnblogs.com/landsol/p/17802255.html

相关文章

  • 《阿凡达:潘多拉边境》PG 电子试玩:重回电影世界的游戏体验
    Ubisoft即将在今年12月发布《阿凡达:潘多拉边境》,这款游戏是基于《阿凡达》电影改编而来,PGSOFT电子游戏玩家将能够深入探索潘朵拉星。游戏延续了电影的宇宙观,玩家需要扮演纳美人,学习他们的文化和价值观。初期体验表明,游戏强调带入感,允许玩家体验与纳美人亲近自然和与生物互动的情......
  • 【专题】数字孪生世界白皮书(2023)报告PDF合集分享(附原数据表)
    原文链接:https://tecdat.cn/?p=34041本次报告合集分为数字孪生综述、技术架构建设、核心技术分享、新型技术成果展示以及重点行业应用五大内容版块。从数字孪生应用建设路径的角度出发,着重提出了“数智视融合,虚实人联动”的观点,并提供数字孪生应用技术的参考。同时,本报告合集还完......
  • Java技术分享:探索无限可能的编程世界
    作为一门广泛应用于软件开发领域的编程语言,Java在近几十年来一直保持着强大的生命力和广泛的影响力。本文将带您深入探索Java技术的各个方面,并分享一些有关Java编程的实用技巧和最新趋势。Java的优势与特点Java作为一种跨平台、面向对象的编程语言,具有许多独特的优势。首先,它的可......
  • 未来世界:16项改变人类社会的新技术
    2016年出版的图书《未来世界:改变人类社会的新技术》,作者是美国的史蒂芬·科特勒(StevenKotler),里面是对各种前沿科技的展望,比如仿生人、机器人、飞行汽车、人工生命、生命延长、行星矿业、意识下载等。史蒂芬·科特勒是《纽约时报》《西线》《大西洋月刊》及《探索》杂志的畅销专......
  • 解密Prompt系列18. LLM Agent之只有智能体的世界
    重新回来聊Agent,前四章的LLMAgent,不论是和数据库和模型还是和搜索引擎交互,更多还是大模型和人之间的交互。这一章我们来唠唠只有大模型智能体的世界!分别介绍斯坦福小镇和Chatdev两篇论文。它们的共同特点是使用多个大模型智能体协同完成任务。多智能相比单一智能体可能有以下的......
  • 我的世界1.20.1模组开发---4.添加方块
    介绍  在游戏中添加方块的方法和之前添加物品的方法类似,都是先通过DeferredRegister.create方法获取对应类型的注册表,然后再把对应的方块添加到注册表中,最后在Mod事件总线上添加该注册表即可。但是由于是方块,会有一些地方和物品不太一样的地方。添加一个方块要分别注册方块和方......
  • 物理世界的互动之旅:Matter.js入门指南
    本文简介戴尬猴,我是德育处主任欢迎来到《物理世界的互动之旅:Matter.js入门指南》。本文将带您探索Matter.js,一个强大而易于使用的JavaScript物理引擎库。我将介绍Matter.js的基本概念,包括引擎、世界、物体和约束等。本文还提供丰富的代码示例,帮助各位工友更好地理解如......
  • 《创新者-一群技术狂人和鬼才程序员如何改变世界》
    IT技术创新的历史经验创新者创新者必须深入理解产品的工程与设计,最优秀的领导人对工程和产品设计理解最为深刻。创新者的一个基本特质是保持专注。创新者应该热爱自己的事业,为之而狂热以至忘我工作。只有在激情的驱使下,创新者才能做出最出色的工作。创新者可以看到既......
  • Generative AI 新世界 | Falcon 40B 开源大模型的部署方式分析
    在上期文章,我们探讨了如何在自定义数据集上来微调(fine-tuned)模型。本期文章,我们将重新回到文本生成的大模型部署场景,探讨如何在AmazonSageMaker上部署具有400亿参数的Falcon40B开源大模型。亚马逊云科技开发者社区为开发者们提供全球的开发技术资源。这里有技术文档、开......
  • 重磅!2023 软科世界大学学术排名发布!中国排名第二
    全球领先的高等教育评价机构软科正式发布「2023软科世界大学学术排名」,排名展示了全球领先的1000所研究型大学,今年中国内地共有191所高校上榜,历史首次超过美国上榜高校数(187所),位列世界第一:其中10所位列世界百强,比去年增加2所。清华大学排名全球第22,位列亚洲第一。北京......