当前位置: 首页 > news >正文

2024HDU Contest 5 Problem 5

题目链接

从大到小枚举gcd的值 d d d,以及编号为 d d d的倍数的点, [ d , 2 d , 3 d , … ] [d,2d,3d,\dots] [d,2d,3d,]
然后对于任何一条边 ( x , y ) (x,y) (x,y),如果 x x x的子树和 y y y的子树里都有编号为 d d d倍数的点,则这条边的答案至少为d。考虑到对于每条边我们只需要知道最大值,所以如果一条边已经在之前的 d d d中被更新过答案,我们就可以将它合并起来。合并的过程可以通过并查集来实现。

所以总结下来做法就是枚举出编号为 d d d的倍数的点之后,将这些点之间的路径都遍历一遍并合并起来。

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+5;
int t,n,f[maxn];
int eu[maxn],ev[maxn];
inline int find(int x){return f[x]==x?f[x]:f[x]=find(f[x]);
}
vector<int> g[maxn];
int par[maxn],dep[maxn];
void dfs(int u,int fa){par[u]=fa;dep[u]=dep[fa]+1;for(auto v:g[u]){if(v==fa)continue;dfs(v,u);}
}
int ind[maxn],ans[maxn];
signed main(){int size(256<<20); //256M__asm__ ( "movq %0, %%rsp\n"::"r"((char*)malloc(size)+size));ios::sync_with_stdio(0);cin.tie(0);//freopen("5.in","r",stdin);//freopen("5.out","w",stdout);cin>>t;while(t--){cin>>n;for(int i=1;i<=n;i++)g[i].clear();for(int i=1;i<n;i++){cin>>eu[i]>>ev[i];g[eu[i]].push_back(ev[i]);g[ev[i]].push_back(eu[i]);}dfs(1,0);for(int i=1;i<n;i++){if(dep[eu[i]]>dep[ev[i]]){ind[eu[i]]=i;}else{ind[ev[i]]=i;}}for(int i=1;i<=n;i++)f[i]=i;for(int d=n/2;d>=1;d--){int x=find(d);for(int j=d+d;j<=n;j+=d){int y=find(j);while(x!=y){if(dep[x]>dep[y])swap(x,y);ans[ind[y]]=d;f[y]=find(par[y]);y=find(par[y]);}}}for(int i=1;i<n;i++)printf("%d ",ans[i]);puts("");}exit(0);//return 0;
}

每条边只会被合并一次,然后枚举倍数的时间开销也是调和级数,所以总复杂度为 O ( n log ⁡ n ) O(n\log n) O(nlogn)

相关文章:

2024HDU Contest 5 Problem 5

题目链接 从大到小枚举gcd的值 d d d&#xff0c;以及编号为 d d d的倍数的点&#xff0c; [ d , 2 d , 3 d , … ] [d,2d,3d,\dots] [d,2d,3d,…]。 然后对于任何一条边 ( x , y ) (x,y) (x,y)&#xff0c;如果 x x x的子树和 y y y的子树里都有编号为 d d d倍数的点&#xf…...

nGQL入门

引言 nGQL&#xff08;NebulaGraph Query Language&#xff09;是用于操作 NebulaGraph 的查询语言。它的语法类似于 Cypher&#xff0c;但有自己独特的特性。以下是一些 nGQL 的基本语法和操作示例&#xff0c;以帮助你入门。 基本概念 节点&#xff08;Vertex&#xff09;…...

[CP_AUTOSAR]_系统服务_DEM模块(二)功能规范介绍

目录 1、DEM 功能规范描述1.1、Startup behavior1.2、Monitor re-initialization 在前面 《[CP_AUTOSAR]_系统服务_DEM模块&#xff08;一&#xff09;》文中&#xff0c;简要介绍了 DEM 模块的功能、与其它模块之间的功能交互&#xff0c;本文将接着介绍 DEM 模块的功能规范。…...

Linux中yum、rpm、apt-get、wget的区别,yum、rpm、apt-get常用命令,CentOS、Ubuntu中安装wget

文章目录 一、常见Linux发行版本二、Linux中yum、rpm、apt-get、wget的区别2.1 yum2.2 rpm2.3 apt-get2.4 wget2.5 总结 三、CentOS中yum的作用3.1 yum清空缓存列表3.2 yum显示信息3.3 yum搜索、查看3.4 yum安装3.5 yum删除、卸载程序3.6 yum包的升级、降级 四、Ubuntu中apt-ge…...

IPython的使用技巧2

关注我&#xff0c;持续分享逻辑思维&管理思维&面试题&#xff1b; 可提供大厂面试辅导、及定制化求职/在职/管理/架构辅导&#xff1b; 推荐专栏《10天学会使用asp.net编程AI大模型》&#xff0c;目前已完成所有内容。一顿烧烤不到的费用&#xff0c;让人能紧跟时代的…...

win10打开程序闪退的解决方法,亲测好用

当我们在使用win10系统的时候&#xff0c;可能会遇到安装某些程序后无法正常使用&#xff0c;一打开就闪退&#xff0c;或者点击右下角图标就消失了&#xff0c;而其他程序却可以正常打开使用。下面小编就来和大家分享亲测好用的win10打开程序闪退的解决办法。 问题原因分析&a…...

木舟0基础学习Java的第二十一天(数据库,MySQL,SQLyog)

数据库 数据库&#xff1a;按照数据结构来组织 存储数据的厂库 数据管理系统(Database Management System,DBMS)&#xff1a;一套操作和管理数据库的软件 用于简历 使用 维护数据库 关系型数据库&#xff1a;采用关系模型作为数据组织方式 逻辑结构是一张二维表 由行和列组成…...

python-鼠标绘画线条程序

闲来无聊简单编写了一个绘图小程序。 主要思路 主要是基于Python中的内置模块turtle编写的&#xff0c;简单扩展了一下&#xff0c;通过绑定事件能够达到鼠标绘制、删除、存储已经绘制图案的线条这几个功能。 路径结构 -draw- define.py- main.py- myturtle.py使用 点住鼠…...

【Python实战】如何优雅地实现 PDF 去水印?

话接上篇&#xff0c;自动化处理 PDF 文档&#xff0c;完美实现 WPS 会员功能 小伙伴们更关心的是如何去除 PDF 中的水印~ 今天&#xff0c;就来分享一个超简单的 PDF 去水印方法~ 1. 原理介绍 在上一篇中&#xff0c;我们介绍了如何将 PDF 文档转换成图片&#xff0c;图片…...

Keysight(原Agilent) E4980AL 精密 LCR 表特性与技术指标

Keysight(原Agilent) E4980AL 精密 LCR 表为基础 LCR 表树立了行业标准&#xff0c;可在多个频率范围内提供更佳的精度、速度和通用性。E4980AL 结合了种类繁多的附件&#xff0c;适用于一般研发和生产环境中的各种元件和材料测量。也可通过频率升级而提升投资回报率。 Keysig…...

【运维】Redis主从复制 配置

【运维】Redis主从复制 配置 主库配置Master # 默认情况下&#xff0c;是 启用保护模式的&#xff0c;其他主机的客户端无法连接到 Redis 。当想要其他主机的客户端连接到 Redis 时&#xff0c;需要修改为 no 。protected-mode no 从库配置Slave # replicaof [master主机ip] …...

C++ 微积分 - 求导 - 自动微分(Automatic Differentiation)

C 微积分 - 求导 - 自动微分&#xff08;Automatic Differentiation&#xff09; flyfish 自动微分&#xff08;Automatic Differentiation&#xff0c;简称 AD&#xff09;是一种用于精确计算函数导数的技术。它结合了符号微分的准确性和数值微分的效率。自动微分的核心思想…...

面试题-每日5道

26.在 Queue 中 poll()和 remove()有什么区别? 相同点&#xff1a;都是删除第一个元素并返回。 不同点&#xff1a;如果没有元素poll()会返回null,而remove()会抛出NoSuchElementException异常 27.哪些集合类是线程安全的&#xff1f; Vector,Stock,Hashtable都是线程安全的&a…...

STM32卡死、跑飞如何调试确定问题

目录 前言 一、程序跑飞原因 二、调试工具 2.1Registers工具 2.2 Memory工具 2.3 Disassembly工具 2.4 Call Stack工具 三、找到程序跑飞位置 方式一、 方式二、 前言 我们初学STM32的时候代码难免会出现疏忽&#xff0c;导致程序跑飞&#xff0c;不再正常运行&#…...

代理模式和Spring MVC

Spring是一个分层的轻量级的开源Java框架。核心是IOC(Inverse of Control 控制反转)和AOP(Aspect Oriented Programming 面向切面编程) AOP 面向切面 AOP &#xff08;Aspect Orient Programming&#xff09;,直译过来就是 面向切面编程&#xff0c;AOP 是一种编程思想&#x…...

深入理解Vue slot的原理

文章目录 前言为什么需要插槽作用域插槽插槽的原理总结 前言 插槽是Vue中一个重要的特性&#xff0c;它有很多种用法&#xff1a;默认插槽、具名插槽、作用域插槽。尤其作用域插槽&#xff0c;还有一堆特性&#xff0c;比如解构prop&#xff0c;解构prop的时候还可以进行属性名…...

git fetch作用与用法

目录 git fetch作用 git fetch用法 git fetch作用 git fetch 命令在 Git 版本控制系统中扮演着重要的角色。其主要作用是从远程仓库获取最新版本的项目文件&#xff0c;但不会自动合并或修改你当前的工作。这意味着&#xff0c;使用 git fetch 后&#xff0c;你需要手动合并…...

pycharm如何查看git历史版本变更信息

通过名字查看不同版本 查看版本不同地方...

【2.2 python中的变量】

2.2 python中的变量 在Python中&#xff0c;变量是存储数据值的容器。Python是一种动态类型语言&#xff0c;这意味着你不需要在声明变量时指定变量的类型&#xff1b;Python会根据你赋给变量的值自动确定其类型。下面我将详细介绍Python中的变量&#xff0c;包括保留字&#…...

Python软体中找出一组字符串的最长公共前缀:算法与实现

Python软体中找出一组字符串的最长公共前缀:算法与实现 在处理字符串数据时,寻找多个字符串之间的共同特征是一个常见的需求。特别是在文件名、URL、或其他文本数据中,找到最长公共前缀(Longest Common Prefix, LCP)可以帮助我们进行更高效的搜索和分类。本文将详细介绍如…...

第19节 Node.js Express 框架

Express 是一个为Node.js设计的web开发框架&#xff0c;它基于nodejs平台。 Express 简介 Express是一个简洁而灵活的node.js Web应用框架, 提供了一系列强大特性帮助你创建各种Web应用&#xff0c;和丰富的HTTP工具。 使用Express可以快速地搭建一个完整功能的网站。 Expre…...

TDengine 快速体验(Docker 镜像方式)

简介 TDengine 可以通过安装包、Docker 镜像 及云服务快速体验 TDengine 的功能&#xff0c;本节首先介绍如何通过 Docker 快速体验 TDengine&#xff0c;然后介绍如何在 Docker 环境下体验 TDengine 的写入和查询功能。如果你不熟悉 Docker&#xff0c;请使用 安装包的方式快…...

Spark 之 入门讲解详细版(1)

1、简介 1.1 Spark简介 Spark是加州大学伯克利分校AMP实验室&#xff08;Algorithms, Machines, and People Lab&#xff09;开发通用内存并行计算框架。Spark在2013年6月进入Apache成为孵化项目&#xff0c;8个月后成为Apache顶级项目&#xff0c;速度之快足见过人之处&…...

线程同步:确保多线程程序的安全与高效!

全文目录&#xff1a; 开篇语前序前言第一部分&#xff1a;线程同步的概念与问题1.1 线程同步的概念1.2 线程同步的问题1.3 线程同步的解决方案 第二部分&#xff1a;synchronized关键字的使用2.1 使用 synchronized修饰方法2.2 使用 synchronized修饰代码块 第三部分&#xff…...

微信小程序 - 手机震动

一、界面 <button type"primary" bindtap"shortVibrate">短震动</button> <button type"primary" bindtap"longVibrate">长震动</button> 二、js逻辑代码 注&#xff1a;文档 https://developers.weixin.qq…...

Linux-07 ubuntu 的 chrome 启动不了

文章目录 问题原因解决步骤一、卸载旧版chrome二、重新安装chorme三、启动不了&#xff0c;报错如下四、启动不了&#xff0c;解决如下 总结 问题原因 在应用中可以看到chrome&#xff0c;但是打不开(说明&#xff1a;原来的ubuntu系统出问题了&#xff0c;这个是备用的硬盘&a…...

高防服务器能够抵御哪些网络攻击呢?

高防服务器作为一种有着高度防御能力的服务器&#xff0c;可以帮助网站应对分布式拒绝服务攻击&#xff0c;有效识别和清理一些恶意的网络流量&#xff0c;为用户提供安全且稳定的网络环境&#xff0c;那么&#xff0c;高防服务器一般都可以抵御哪些网络攻击呢&#xff1f;下面…...

Spring AI与Spring Modulith核心技术解析

Spring AI核心架构解析 Spring AI&#xff08;https://spring.io/projects/spring-ai&#xff09;作为Spring生态中的AI集成框架&#xff0c;其核心设计理念是通过模块化架构降低AI应用的开发复杂度。与Python生态中的LangChain/LlamaIndex等工具类似&#xff0c;但特别为多语…...

Linux C语言网络编程详细入门教程:如何一步步实现TCP服务端与客户端通信

文章目录 Linux C语言网络编程详细入门教程&#xff1a;如何一步步实现TCP服务端与客户端通信前言一、网络通信基础概念二、服务端与客户端的完整流程图解三、每一步的详细讲解和代码示例1. 创建Socket&#xff08;服务端和客户端都要&#xff09;2. 绑定本地地址和端口&#x…...

RabbitMQ入门4.1.0版本(基于java、SpringBoot操作)

RabbitMQ 一、RabbitMQ概述 RabbitMQ RabbitMQ最初由LShift和CohesiveFT于2007年开发&#xff0c;后来由Pivotal Software Inc.&#xff08;现为VMware子公司&#xff09;接管。RabbitMQ 是一个开源的消息代理和队列服务器&#xff0c;用 Erlang 语言编写。广泛应用于各种分布…...