Leetcode 2867. Count Valid Paths in a Tree
- Leetcode 2867. Count Valid Paths in a Tree
- 1. 解题思路
- 2. 代码实现
- 题目链接:2867. Count Valid Paths in a Tree
1. 解题思路
这一题思路上的话由于要求路径上有且仅有一个质数点,因此,一个直接的思路就是考察所有质数的点作为中心点时,其辐射出去的非质数点的个数。
假设一个质数点 p p p上有 k k k个合数子节点,然后每一个合数子节点对应的只包含合数的子树当中的节点个数分别为 n 1 , ⋯ n k n_1, \cdots n_k n1,⋯nk个,那么,包含且仅包含 p p p的路径个数为:
- p p p作为路径的一个节点: N = ∑ i = 1 k n i N = \sum\limits_{i=1}^{k}n_i N=i=1∑kni
- p p p作为路径的一个中间节点: N = ∑ i = 1 k ∑ j = 1 , j ≠ i k n i × n j = ∑ i = 1 k n i ( ∑ j = 1 k n j − n i ) / 2 N = \sum\limits_{i=1}^{k}\sum\limits_{j=1, j\neq i}^{k} n_i \times n_j=\sum\limits_{i=1}^{k}n_i(\sum\limits_{j=1}^{k}n_j - n_i) / 2 N=i=1∑kj=1,j=i∑kni×nj=i=1∑kni(j=1∑knj−ni)/2
由此,问题就转化为只要求得每一个质数节点 p p p周围相邻的合数节点 u u u作为根节点时的只包含合数节点的子树的节点的个数。
而这个问题只需要用一个深度优先遍历就可以完成了。当然,为了优化执行效率,我们加上了一个cache来对其进行优化。
2. 代码实现
给出最终的python代码实现如下:
@lru_cache(None)
def get_primes():n = 10**5status = [0 for _ in range(n)]primes = []for i in range(2, n):if status[i] == 1:continueprimes.append(i)for j in range(i, n, i):status[j] = 1return primesPRIMES = get_primes()class Solution:def countPaths(self, n: int, edges: List[List[int]]) -> int:if n == 1:return 0primes = PRIMES[:bisect.bisect_right(PRIMES, n)]prime_set = set(primes)graph = defaultdict(list)for u, v in edges:graph[u].append(v)graph[v].append(u)@lru_cache(None)def dfs(u, pre):res = 1for v in graph[u]:if v != pre and v not in prime_set:res += dfs(v, u)return resdef query(u):nodes = [dfs(v, -1) for v in graph[u] if v not in prime_set]res = 0s = sum(nodes)for k in nodes:res += k * (s-k)return res // 2 + sreturn sum(query(u) for u in primes)
提交代码评测得到:耗时1683ms,占用内存71.2MB。
相关文章:
Leetcode 2867. Count Valid Paths in a Tree
Leetcode 2867. Count Valid Paths in a Tree 1. 解题思路2. 代码实现 题目链接:2867. Count Valid Paths in a Tree 1. 解题思路 这一题思路上的话由于要求路径上有且仅有一个质数点,因此,一个直接的思路就是考察所有质数的点作为中心点时…...
Jtti:Ubuntu下如何创建XFS文件系统的LVM
在 Ubuntu 下创建一个 XFS 文件系统的 LVM(Logical Volume Manager)分区需要一系列步骤。以下是详细的步骤: 1. 创建物理卷 (PV) 首先,将要用于 LVM 的硬盘分区(物理卷)初始化为物理卷。假设你有一个硬盘…...
做销售管理分析需要看哪些关键指标?
做销售管理分析需要看哪些关键指标? 销售管理分析时抓取关键指标,有着能够【分析和判断销售趋势、为销售决策提供数据支持、优化销售流程和客户管理】等的好处 在了解了分析关键指标的目的之后,我们就可以根据企业的需求来确定关键指标&…...
【Python】自动完成手写字体图片贴入以及盖章工具
简介 该工具完成了如下功能: 1.将文字转换为手写体填入到模板文件中 2.自动将文字转换为盖章格式填入到模板文件中 3.字体格式可以替换 4.有配置文件进行扩展功能 功能模块 1.界面模块 import sys from PyQt5.QtWidgets import QApplication, QMessageBox, QWid…...
基于Xml方式Bean的配置-初始化方法和销毁方法
SpringBean的配置详解 Bean的初始化和销毁方法配置 Bean在被实例化后,可以执行指定的初始化方法完成一些初始化的操作,Bean在销毁之前也可以执行指定的销毁方法完成一些操作,初始化方法名称和销毁方法名称通过 <bean id"userService…...
实时更新进度条:JavaScript中的定时器和异步编程技巧
前言 在Web开发中,有许多场景需要实时地更新页面上的进度,例如上传文件、数据处理等。本文将介绍如何利用JavaScript中的定时器和异步编程技巧来实现实时更新进度,并探讨一些其他解决方案。 处理进度实时更新: 利用异步编程实现实…...
【简单图论】CF898 div4 H
Problem - H - Codeforces 题意: 思路: 手玩一下样例就能发现简单结论: v 离它所在的树枝的根的距离 < m 离这个根的距离时是 YES 否则就是NO 实现就很简单,先去树上找环,然后找出这个根,分别给a 和…...
【大虾送书第十一期】适合新手自学的网络安全基础技能“蓝宝书”:《CTF那些事儿》
目录 🥮写在前面 🥮内容简介 🥮读者对象 🥮专家推荐 🥮目录 🥮文末福利 🦐博客主页:大虾好吃吗的博客 🦐专栏地址:免费送书活动专栏地址 写在前面 CTF比赛是快…...
IDEA安装离线插件后重启无法打开
解决方法 1.找到插件安装目录删除插件 插件的位置一般在C:\Users\19058\AppData\Roaming\JetBrains\IntelliJIdea2021.1\plugins 高亮部分是自己电脑的用户位置,把报错前的刚才最新安装的插件删除,再尝试打开idea即可解决该问题 2.补充说明 AppData是个隐…...
论软件的可靠性设计
摘要 2021年6月,我所在的公司中标某集团保险大数据平台一体化研发项目,该项目总投资2000万人民币,项目周期为2年,通过该项目,搭建该集团保险大数据平台,一方面将全国所有保险业务全部入库并保存࿰…...
AG35学习笔记(一):debug串口抓取模组log、debug串口测试AT指令、echo命令通过串口发送16进制数据
目录 一、概述二、抓取模组log2.1 硬件接口2.2 用户登录2.3 相关指令 三、测试AT指令3.1 查看端口3.2 进入模式 四、串口发16进制echo使用 一、概述 二、抓取模组log 在之前记录了通过USB,使用移远工具Qwinlog来抓取log(3.3 抓取模组log)。…...
Python进阶学习----一闭三器
目录 编辑 前言 一.三器 1. 迭代器(Iterator) 1.1 什么是可迭代对象 1.2什么是迭代器 1.3案例演示: 以下是一个简单的迭代器示例,遍历一个列表并打印每个元素: 1.4迭代器总结 2. 生成器(Generat…...
C/S架构学习之TCP客户端
TCP客户端的实现流程:一、创建套接字(socket函数):通信域选择IPV4网络协议、流式套接字; int sockfd socket(AF_INET,SOCK_STREAM,0); 二、填充服务器的网络信息结构体(struct sockaddr_in serveraddr&…...
系统集成|第十二章(笔记)
目录 第十二章 沟通管理12.1 沟通的基本概念12.2 主要过程12.2.1 规划沟通管理12.2.2 管理沟通12.2.3 控制沟通 12.3 常见问题 上篇:第十一章、项目人力资源管理 第十二章 沟通管理 沟通管理在项目计划、执行、监控过程中具有重要的作用,项目经理应该拿…...
图神经网络(GNN)最新顶会论文汇总【附源码】
得益于强大的建模和分析能力,图神经网络(GNN)在社交网络分析、推荐系统、知识图谱、文本分析、等诸多领域得到了广泛的应用,目前已成为了人工智能领域的热门研究方向。 在今年的各大顶会获奖论文中,图神经网络相关的论…...
【算法】算法设计与分析 课程笔记 第二章 递归与分治策略
2.1 递归 直接或间接地调用自身的算法称为递归算法。 用函数自身给出定义的函数称为递归函数。 2.1.1 阶乘 首先得想到一个求阶乘的函数: 这个函数的下面那个式子就用到了调用自身,所以可以用递归来实现,将主问题拆分成若干层的子问题&am…...
Java客户端_Apache Curator操作Zookeeper
Curator是 Netflix公司开源的一套ZooKeeper客户端框架。和ZkClient一样,Curator解决了很多ZooKeeper客户端非常底层的细节开发工作,包括连接重连、反复注册Watcher和 NodeExistsException异常等,目前已经成为了Apache的顶级项目,是全世界范围…...
14:00面试,14:07就出来了,问的问题有点变态
从小厂出来,没想到在另一家公司又寄了。 到这家公司开始上班,加班是每天必不可少的,看在钱给的比较多的份上,就不太计较了。没想到8月一纸通知,所有人不准加班,加班费不仅没有了,薪资还要降40%,…...
《你好,C语言》:从另一个视角学习并重新审视C语言的意义
《你好,C语言》:从另一个视角学习并重新审视C语言的意义 尽管C语言诞生了这么多年,但是它依然活跃在开发者一线,不可否认的是C语言的确有它独特的魅力。本文将从一个全新的视角,重新带领大家学习领悟C语言的奥秘&#…...
信创之国产浪潮电脑+统信UOS操作系统体验1:硬件及软件常规功能支持情况介绍
一、引言 由于公司要求支持国产信创,最近办公的笔记本电脑换成了软硬件全国产,由于国产操作系统是在开源linux基础上演进的,在换之前,非常担心操作不方便,周边应用软件少,功能差,内心是比较抗拒…...
如何将联系人从 iPhone 转移到 Android
从 iPhone 换到 Android 手机时,你可能需要保留重要的数据,例如通讯录。好在,将通讯录从 iPhone 转移到 Android 手机非常简单,你可以从本文中学习 6 种可靠的方法,确保随时保持连接,不错过任何信息。 第 1…...
服务器--宝塔命令
一、宝塔面板安装命令 ⚠️ 必须使用 root 用户 或 sudo 权限执行! sudo su - 1. CentOS 系统: yum install -y wget && wget -O install.sh http://download.bt.cn/install/install_6.0.sh && sh install.sh2. Ubuntu / Debian 系统…...
【Linux】Linux 系统默认的目录及作用说明
博主介绍:✌全网粉丝23W,CSDN博客专家、Java领域优质创作者,掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域✌ 技术范围:SpringBoot、SpringCloud、Vue、SSM、HTML、Nodejs、Python、MySQL、PostgreSQL、大数据、物…...
GO协程(Goroutine)问题总结
在使用Go语言来编写代码时,遇到的一些问题总结一下 [参考文档]:https://www.topgoer.com/%E5%B9%B6%E5%8F%91%E7%BC%96%E7%A8%8B/goroutine.html 1. main()函数默认的Goroutine 场景再现: 今天在看到这个教程的时候,在自己的电…...
JDK 17 序列化是怎么回事
如何序列化?其实很简单,就是根据每个类型,用工厂类调用。逐个完成。 没什么漂亮的代码,只有有效、稳定的代码。 代码中调用toJson toJson 代码 mapper.writeValueAsString ObjectMapper DefaultSerializerProvider 一堆实…...
Java后端检查空条件查询
通过抛出运行异常:throw new RuntimeException("请输入查询条件!");BranchWarehouseServiceImpl.java // 查询试剂交易(入库/出库)记录Overridepublic List<BranchWarehouseTransactions> queryForReagent(Branch…...
webpack面试题
面试题:webpack介绍和简单使用 一、webpack(模块化打包工具)1. webpack是把项目当作一个整体,通过给定的一个主文件,webpack将从这个主文件开始找到你项目当中的所有依赖文件,使用loaders来处理它们&#x…...
Java并发编程实战 Day 11:并发设计模式
【Java并发编程实战 Day 11】并发设计模式 开篇 这是"Java并发编程实战"系列的第11天,今天我们聚焦于并发设计模式。并发设计模式是解决多线程环境下常见问题的经典解决方案,它们不仅提供了优雅的设计思路,还能显著提升系统的性能…...
JUC并发编程(二)Monitor/自旋/轻量级/锁膨胀/wait/notify/锁消除
目录 一 基础 1 概念 2 卖票问题 3 转账问题 二 锁机制与优化策略 0 Monitor 1 轻量级锁 2 锁膨胀 3 自旋 4 偏向锁 5 锁消除 6 wait /notify 7 sleep与wait的对比 8 join原理 一 基础 1 概念 临界区 一段代码块内如果存在对共享资源的多线程读写操作…...
八、【ESP32开发全栈指南:UDP客户端】
1. 环境准备 安装ESP-IDF v4.4 (官方指南)确保Python 3.7 和Git已安装 2. 创建项目 idf.py create-project udp_client cd udp_client3. 完整优化代码 (main/main.c) #include <string.h> #include "freertos/FreeRTOS.h" #include "freertos/task.h&…...
