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基础上演进的,在换之前,非常担心操作不方便,周边应用软件少,功能差,内心是比较抗拒…...
SpringBoot-17-MyBatis动态SQL标签之常用标签
文章目录 1 代码1.1 实体User.java1.2 接口UserMapper.java1.3 映射UserMapper.xml1.3.1 标签if1.3.2 标签if和where1.3.3 标签choose和when和otherwise1.4 UserController.java2 常用动态SQL标签2.1 标签set2.1.1 UserMapper.java2.1.2 UserMapper.xml2.1.3 UserController.ja…...
Linux链表操作全解析
Linux C语言链表深度解析与实战技巧 一、链表基础概念与内核链表优势1.1 为什么使用链表?1.2 Linux 内核链表与用户态链表的区别 二、内核链表结构与宏解析常用宏/函数 三、内核链表的优点四、用户态链表示例五、双向循环链表在内核中的实现优势5.1 插入效率5.2 安全…...
大型活动交通拥堵治理的视觉算法应用
大型活动下智慧交通的视觉分析应用 一、背景与挑战 大型活动(如演唱会、马拉松赛事、高考中考等)期间,城市交通面临瞬时人流车流激增、传统摄像头模糊、交通拥堵识别滞后等问题。以演唱会为例,暖城商圈曾因观众集中离场导致周边…...
python/java环境配置
环境变量放一起 python: 1.首先下载Python Python下载地址:Download Python | Python.org downloads ---windows -- 64 2.安装Python 下面两个,然后自定义,全选 可以把前4个选上 3.环境配置 1)搜高级系统设置 2…...
数据链路层的主要功能是什么
数据链路层(OSI模型第2层)的核心功能是在相邻网络节点(如交换机、主机)间提供可靠的数据帧传输服务,主要职责包括: 🔑 核心功能详解: 帧封装与解封装 封装: 将网络层下发…...
Java面试专项一-准备篇
一、企业简历筛选规则 一般企业的简历筛选流程:首先由HR先筛选一部分简历后,在将简历给到对应的项目负责人后再进行下一步的操作。 HR如何筛选简历 例如:Boss直聘(招聘方平台) 直接按照条件进行筛选 例如:…...
Java + Spring Boot + Mybatis 实现批量插入
在 Java 中使用 Spring Boot 和 MyBatis 实现批量插入可以通过以下步骤完成。这里提供两种常用方法:使用 MyBatis 的 <foreach> 标签和批处理模式(ExecutorType.BATCH)。 方法一:使用 XML 的 <foreach> 标签ÿ…...
MFC 抛体运动模拟:常见问题解决与界面美化
在 MFC 中开发抛体运动模拟程序时,我们常遇到 轨迹残留、无效刷新、视觉单调、物理逻辑瑕疵 等问题。本文将针对这些痛点,详细解析原因并提供解决方案,同时兼顾界面美化,让模拟效果更专业、更高效。 问题一:历史轨迹与小球残影残留 现象 小球运动后,历史位置的 “残影”…...
【JavaSE】多线程基础学习笔记
多线程基础 -线程相关概念 程序(Program) 是为完成特定任务、用某种语言编写的一组指令的集合简单的说:就是我们写的代码 进程 进程是指运行中的程序,比如我们使用QQ,就启动了一个进程,操作系统就会为该进程分配内存…...
GitHub 趋势日报 (2025年06月06日)
📊 由 TrendForge 系统生成 | 🌐 https://trendforge.devlive.org/ 🌐 本日报中的项目描述已自动翻译为中文 📈 今日获星趋势图 今日获星趋势图 590 cognee 551 onlook 399 project-based-learning 348 build-your-own-x 320 ne…...
