当前位置: 首页 > 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)可以帮助我们进行更高效的搜索和分类。本文将详细介绍如…...

别再自己造轮子了!用Python HAPI一键搞定HITRAN/HITEMP光谱计算(附避坑指南)

别再重复造轮子&#xff01;用Python HAPI高效处理HITRAN/HITEMP光谱数据 在光谱分析领域&#xff0c;许多研究者都曾陷入过这样的困境&#xff1a;为了计算某种气体的光谱特性&#xff0c;花费数周甚至数月时间研读文献、编写算法&#xff0c;结果却发现计算效率低下且结果难以…...

Ncorr 2D:开源数字图像相关技术的架构解析与工程实现

Ncorr 2D&#xff1a;开源数字图像相关技术的架构解析与工程实现 【免费下载链接】ncorr_2D_matlab 2D Digital Image Correlation Matlab Software 项目地址: https://gitcode.com/gh_mirrors/nc/ncorr_2D_matlab 在材料力学、生物医学和结构工程领域&#xff0c;精确测…...

Go代码越容易被AI写,Go工程师越值钱

Go代码越容易被AI写&#xff0c;Go工程师越值钱。 这句话听起来矛盾&#xff0c;但它是这个系列的终极结论。 前提是——你的价值不在"写代码"。 这是「AI工程时代三部曲」的收官篇。第一篇我们聊了Agent框架设计为什么比模型选型更重要&#xff0c;第二篇聊了技术债…...

HunyuanVideo-Foley企业应用:汽车HMI人机交互音效AI生成平台

HunyuanVideo-Foley企业应用&#xff1a;汽车HMI人机交互音效AI生成平台 1. 产品概述 HunyuanVideo-Foley是一款专为企业级音视频生成需求设计的AI平台&#xff0c;特别针对汽车HMI&#xff08;人机交互界面&#xff09;音效场景进行了深度优化。该平台基于RTX 4090D 24GB显存…...

英集芯-IP5316、IP5219有什么区别?详细总结一下

简介 IP5219和IP5316都是英集芯的充电管理IC,两款移动电源SOC芯片输出/输入参数基本一致,但是使用起来却有一些差异,下面就对两款IC使用中遇到的一些问题做一些总结。 IP5219:2.1A 充电 2.4A 放电集成 TYPE_C 协议移动电源 SOC; IP5316:集成 TYPE_C 协议的 2.4A 充电/2.4…...

HackTricks数字取证方法论:内存转储分析与恶意软件检测完全指南

HackTricks数字取证方法论&#xff1a;内存转储分析与恶意软件检测完全指南 【免费下载链接】hacktricks Welcome to the page where you will find each trick/technique/whatever I have learnt in CTFs, real life apps, and reading researches and news. 项目地址: http…...

蓝牙天线匹配避坑指南:从VNA测试到π型电路焊接的5个关键步骤

蓝牙天线匹配避坑指南&#xff1a;从VNA测试到π型电路焊接的5个关键步骤 在消费电子领域&#xff0c;2.4GHz蓝牙天线的性能直接决定了产品的无线连接质量。许多硬件团队在开发过程中常遇到信号不稳定、传输距离短等问题&#xff0c;其核心往往在于天线阻抗匹配的细节处理不当。…...

OpenClaw技能开发入门:基于百川2-13B-4bits制作天气查询插件

OpenClaw技能开发入门&#xff1a;基于百川2-13B-4bits制作天气查询插件 1. 为什么选择OpenClaw开发个人技能&#xff1f; 去年冬天&#xff0c;我每天早上都要手动查询天气决定穿衣厚度&#xff0c;直到发现OpenClaw可以通过自然语言指令自动完成这类重复任务。作为一个开源…...

2026最权威AI论文平台榜单:这些被高校和导师悄悄推荐的工具你还没用?

AI论文平台正成为学术研究的重要助力工具&#xff0c;其在提升写作效率、确保内容合规性方面展现出显著价值。依托权威检测机构、高校实测数据及用户真实反馈&#xff0c;2026年最值得信赖的AI论文平台已逐渐浮出水面&#xff0c;它们不仅功能全面&#xff0c;更深度适配中文论…...

引入电转气协同的含碳捕集与垃圾焚烧虚拟电厂优化调度

【文章复现 可】计及电转气协同的含碳捕集与垃圾焚烧 虚拟电厂优化调度 引入碳捕集电厂–电转气–燃气机组协同利用框架&#xff0c;碳捕集的 CO2可作为电转气原料&#xff0c;生成的天然气则供应给燃气机组&#xff1b;并通过联合调度将碳捕集能耗和烟气处理能耗进行负荷转移…...