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基础上演进的,在换之前,非常担心操作不方便,周边应用软件少,功能差,内心是比较抗拒…...
<6>-MySQL表的增删查改
目录 一,create(创建表) 二,retrieve(查询表) 1,select列 2,where条件 三,update(更新表) 四,delete(删除表…...
【2025年】解决Burpsuite抓不到https包的问题
环境:windows11 burpsuite:2025.5 在抓取https网站时,burpsuite抓取不到https数据包,只显示: 解决该问题只需如下三个步骤: 1、浏览器中访问 http://burp 2、下载 CA certificate 证书 3、在设置--隐私与安全--…...
【Zephyr 系列 10】实战项目:打造一个蓝牙传感器终端 + 网关系统(完整架构与全栈实现)
🧠关键词:Zephyr、BLE、终端、网关、广播、连接、传感器、数据采集、低功耗、系统集成 📌目标读者:希望基于 Zephyr 构建 BLE 系统架构、实现终端与网关协作、具备产品交付能力的开发者 📊篇幅字数:约 5200 字 ✨ 项目总览 在物联网实际项目中,**“终端 + 网关”**是…...
C++.OpenGL (10/64)基础光照(Basic Lighting)
基础光照(Basic Lighting) 冯氏光照模型(Phong Lighting Model) #mermaid-svg-GLdskXwWINxNGHso {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-GLdskXwWINxNGHso .error-icon{fill:#552222;}#mermaid-svg-GLd…...
python执行测试用例,allure报乱码且未成功生成报告
allure执行测试用例时显示乱码:‘allure’ �����ڲ����ⲿ���Ҳ���ǿ�&am…...
【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的“no matching...“系列算法协商失败问题
【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的"no matching..."系列算法协商失败问题 摘要: 近期,在使用较新版本的OpenSSH客户端连接老旧SSH服务器时,会遇到 "no matching key exchange method found", "n…...
腾讯云V3签名
想要接入腾讯云的Api,必然先按其文档计算出所要求的签名。 之前也调用过腾讯云的接口,但总是卡在签名这一步,最后放弃选择SDK,这次终于自己代码实现。 可能腾讯云翻新了接口文档,现在阅读起来,清晰了很多&…...
多模态图像修复系统:基于深度学习的图片修复实现
多模态图像修复系统:基于深度学习的图片修复实现 1. 系统概述 本系统使用多模态大模型(Stable Diffusion Inpainting)实现图像修复功能,结合文本描述和图片输入,对指定区域进行内容修复。系统包含完整的数据处理、模型训练、推理部署流程。 import torch import numpy …...
MySQL:分区的基本使用
目录 一、什么是分区二、有什么作用三、分类四、创建分区五、删除分区 一、什么是分区 MySQL 分区(Partitioning)是一种将单张表的数据逻辑上拆分成多个物理部分的技术。这些物理部分(分区)可以独立存储、管理和优化,…...
c# 局部函数 定义、功能与示例
C# 局部函数:定义、功能与示例 1. 定义与功能 局部函数(Local Function)是嵌套在另一个方法内部的私有方法,仅在包含它的方法内可见。 • 作用:封装仅用于当前方法的逻辑,避免污染类作用域,提升…...
