题目链接
题目大意
给出一棵树，树上每个节点都有一种颜色，求所有颜色相同的节点两两之间距离的总和。
题解
想来写题解主要是看了一下官方解法都写的需要“重心分解”，应该是对应中文语境下的树的点分治。实际上点分治写起来很费事，可以用启发式合并替代。
具体来说，dfs时每个节点都维护一个数据结构（平衡树线段树都可以）用来统计子树下各个颜色节点的数量，维护时启发式合并即可，缺点是复杂度应该是两个logn的。
为了统计答案，除了维护节点数量还需要一边统计他们的深度之和。
代码链接（用小号打的hhh）
ABC359 G - Sum of Tree Distance
news/2024/6/30 18:20:06
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.hjln.cn/news/48525.html
如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈，一经查实，立即删除！相关文章
Spring Boot
第一个SpringBoot应用
项目结构根package：com.zyj.learnSpringBoot要求main()方法所在启动类放在根package下Application
@SpringBootApplication
public class Application {public static void main(String[] args) throws Exception {SpringApplication.run(Application.cl…
Linux 中 根据SRA号获取下载链接
001、使用srapath命令[root@PC1 test2]# srapath SRR1482463
https://sra-pub-run-odp.s3.amazonaws.com/sra/SRR1482463/SRR1482463
[root@PC1 test2]# srapath SRR1770413
https://sra-pub-run-odp.s3.amazonaws.com/sra/SRR1770413/SRR1770413 。
.Net Aspire初体验
Aspire今天参加了Post Microsoft Build & AI Day深圳的集会，众多大佬分享了非常优质前沿的技术和实践，实在受益良多，为了消化吸收关于张队分享的.Net Aspire的内容，特实操一遍小示例并记录如下：
1、以VS2022为例，先升级到最新的版本v17.10.3，新建.NET Aspire Starte…
万象革新，开启鸿蒙原生应用生态新篇章
摘要：星河璀璨，加入鸿蒙正当时。鸿蒙生态应用分发带来新流量、新服务、新能力，携手开发者实现技术生态和价值回报的双赢。
在当下，包括智能手机、平板电脑和穿戴设备在内的华为终端产品连接了亿万用户。这一市场覆盖优势使得自2019年鸿蒙系统首次发布以来，其生态用户基数便…
可能是全网最适合入门的面向对象编程教程：Python实现-嵌入式爱好者必看！
为了帮助初学者更好地理解和应用面向对象的设计方法，本文档更加深入地探讨其背后的原理和特点，并结合实际案例来展示其在实际开发中的应用价值。本文档主要介绍如何使用 Python 进行面向对象编程，需要读者对 Python 语法和单片机开发具有基本了解。相比其他讲解 Python 面向…
MySQL8-中文参考-三-
MySQL8 中文参考（三）原文：docs.oracle.com/javase/tutorial/reallybigindex.html2.8.7 MySQL 源配置选项原文：dev.mysql.com/doc/refman/8.0/en/source-configuration-options.htmlCMake程序提供了对如何配置 MySQL 源分发的大量控制。通常，您可以使用CMake命令行上的选项…
arkTS 如何解析MD格式？
arkTS 如何解析MD格式？1. 尝试1
interface Interface_1 {heading: RegExp;listItem: RegExp;paragraph: RegExp;
}const markdownRules: Interface_1 = {heading: /^#\s+(.*)$/,listItem: /^\s*-\s+(.*)$/,paragraph: /^([^\n]+)$/,
}// 解析 Markdown 文本
function parseMar…