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,以及编号为 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倍数的点…...
nGQL入门
引言 nGQL(NebulaGraph Query Language)是用于操作 NebulaGraph 的查询语言。它的语法类似于 Cypher,但有自己独特的特性。以下是一些 nGQL 的基本语法和操作示例,以帮助你入门。 基本概念 节点(Vertex)…...
[CP_AUTOSAR]_系统服务_DEM模块(二)功能规范介绍
目录 1、DEM 功能规范描述1.1、Startup behavior1.2、Monitor re-initialization 在前面 《[CP_AUTOSAR]_系统服务_DEM模块(一)》文中,简要介绍了 DEM 模块的功能、与其它模块之间的功能交互,本文将接着介绍 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
关注我,持续分享逻辑思维&管理思维&面试题; 可提供大厂面试辅导、及定制化求职/在职/管理/架构辅导; 推荐专栏《10天学会使用asp.net编程AI大模型》,目前已完成所有内容。一顿烧烤不到的费用,让人能紧跟时代的…...
win10打开程序闪退的解决方法,亲测好用
当我们在使用win10系统的时候,可能会遇到安装某些程序后无法正常使用,一打开就闪退,或者点击右下角图标就消失了,而其他程序却可以正常打开使用。下面小编就来和大家分享亲测好用的win10打开程序闪退的解决办法。 问题原因分析&a…...
木舟0基础学习Java的第二十一天(数据库,MySQL,SQLyog)
数据库 数据库:按照数据结构来组织 存储数据的厂库 数据管理系统(Database Management System,DBMS):一套操作和管理数据库的软件 用于简历 使用 维护数据库 关系型数据库:采用关系模型作为数据组织方式 逻辑结构是一张二维表 由行和列组成…...
python-鼠标绘画线条程序
闲来无聊简单编写了一个绘图小程序。 主要思路 主要是基于Python中的内置模块turtle编写的,简单扩展了一下,通过绑定事件能够达到鼠标绘制、删除、存储已经绘制图案的线条这几个功能。 路径结构 -draw- define.py- main.py- myturtle.py使用 点住鼠…...
【Python实战】如何优雅地实现 PDF 去水印?
话接上篇,自动化处理 PDF 文档,完美实现 WPS 会员功能 小伙伴们更关心的是如何去除 PDF 中的水印~ 今天,就来分享一个超简单的 PDF 去水印方法~ 1. 原理介绍 在上一篇中,我们介绍了如何将 PDF 文档转换成图片,图片…...
Keysight(原Agilent) E4980AL 精密 LCR 表特性与技术指标
Keysight(原Agilent) E4980AL 精密 LCR 表为基础 LCR 表树立了行业标准,可在多个频率范围内提供更佳的精度、速度和通用性。E4980AL 结合了种类繁多的附件,适用于一般研发和生产环境中的各种元件和材料测量。也可通过频率升级而提升投资回报率。 Keysig…...
【运维】Redis主从复制 配置
【运维】Redis主从复制 配置 主库配置Master # 默认情况下,是 启用保护模式的,其他主机的客户端无法连接到 Redis 。当想要其他主机的客户端连接到 Redis 时,需要修改为 no 。protected-mode no 从库配置Slave # replicaof [master主机ip] …...
C++ 微积分 - 求导 - 自动微分(Automatic Differentiation)
C 微积分 - 求导 - 自动微分(Automatic Differentiation) flyfish 自动微分(Automatic Differentiation,简称 AD)是一种用于精确计算函数导数的技术。它结合了符号微分的准确性和数值微分的效率。自动微分的核心思想…...
面试题-每日5道
26.在 Queue 中 poll()和 remove()有什么区别? 相同点:都是删除第一个元素并返回。 不同点:如果没有元素poll()会返回null,而remove()会抛出NoSuchElementException异常 27.哪些集合类是线程安全的? Vector,Stock,Hashtable都是线程安全的&a…...
STM32卡死、跑飞如何调试确定问题
目录 前言 一、程序跑飞原因 二、调试工具 2.1Registers工具 2.2 Memory工具 2.3 Disassembly工具 2.4 Call Stack工具 三、找到程序跑飞位置 方式一、 方式二、 前言 我们初学STM32的时候代码难免会出现疏忽,导致程序跑飞,不再正常运行&#…...
代理模式和Spring MVC
Spring是一个分层的轻量级的开源Java框架。核心是IOC(Inverse of Control 控制反转)和AOP(Aspect Oriented Programming 面向切面编程) AOP 面向切面 AOP (Aspect Orient Programming),直译过来就是 面向切面编程,AOP 是一种编程思想&#x…...
深入理解Vue slot的原理
文章目录 前言为什么需要插槽作用域插槽插槽的原理总结 前言 插槽是Vue中一个重要的特性,它有很多种用法:默认插槽、具名插槽、作用域插槽。尤其作用域插槽,还有一堆特性,比如解构prop,解构prop的时候还可以进行属性名…...
git fetch作用与用法
目录 git fetch作用 git fetch用法 git fetch作用 git fetch 命令在 Git 版本控制系统中扮演着重要的角色。其主要作用是从远程仓库获取最新版本的项目文件,但不会自动合并或修改你当前的工作。这意味着,使用 git fetch 后,你需要手动合并…...
pycharm如何查看git历史版本变更信息
通过名字查看不同版本 查看版本不同地方...
【2.2 python中的变量】
2.2 python中的变量 在Python中,变量是存储数据值的容器。Python是一种动态类型语言,这意味着你不需要在声明变量时指定变量的类型;Python会根据你赋给变量的值自动确定其类型。下面我将详细介绍Python中的变量,包括保留字&#…...
Python软体中找出一组字符串的最长公共前缀:算法与实现
Python软体中找出一组字符串的最长公共前缀:算法与实现 在处理字符串数据时,寻找多个字符串之间的共同特征是一个常见的需求。特别是在文件名、URL、或其他文本数据中,找到最长公共前缀(Longest Common Prefix, LCP)可以帮助我们进行更高效的搜索和分类。本文将详细介绍如…...
iOSDeviceSupport终极指南:如何快速解决Xcode设备支持文件缺失问题
iOSDeviceSupport终极指南:如何快速解决Xcode设备支持文件缺失问题 【免费下载链接】iOSDeviceSupport All versions of iOS Device Support 项目地址: https://gitcode.com/gh_mirrors/ios/iOSDeviceSupport 你是否曾经在iOS开发中遇到过这样的困扰…...
构建个人技能知识库:从Markdown管理到自动化实践
1. 项目概述:一个技能库的诞生与价值最近在整理个人知识体系时,我一直在思考一个问题:如何将那些零散的、跨领域的“技能点”系统化地管理起来,形成一个可以持续迭代、随时取用的个人工具箱?这不仅仅是写一份简历上的技…...
【AI智能体】OpenClaw 本地 数字员工 Windows 快速搭建方法
OpenClaw(小龙虾)是一款备受开发者关注的开源本地 AI 智能体,凭借本地运行、零代码操作、自动执行电脑任务等特点快速普及。它不只是对话 AI,更是能够直接操控系统的自动化工具,可根据自然语言指令完成任务拆解、工具调…...
基于语义的代码搜索工具Hypergrep:从AST解析到智能调用链分析
1. 项目概述:为什么我们需要一个“更聪明”的代码搜索工具? 如果你和我一样,每天都要在动辄几十万行、横跨多个模块和语言的代码仓库里“大海捞针”,那你肯定对传统的 grep 或 IDE 的全局搜索又爱又恨。爱的是它们简单直接&…...
基于RAG与向量检索的本地化智能搜索问答系统部署指南
1. 项目概述与核心价值最近在折腾一个挺有意思的开源项目,叫moneykick/openclaw-anspire-search_pro。光看这个名字,可能有点摸不着头脑,但如果你对信息检索、智能问答或者企业知识库构建感兴趣,那这个项目绝对值得你花时间研究一…...
边缘计算大模型部署实战:从LLaMA量化到树莓派推理优化
1. 项目概述:一个为边缘计算优化的轻量级大语言模型最近在折腾边缘设备上的AI应用,发现一个挺有意思的项目——KuiperLLama。这名字听起来就很有“边缘”感,Kuiper(柯伊伯带)是太阳系边缘的一个区域,用它来…...
魔兽争霸3终极优化指南:WarcraftHelper 2024免费配置教程
魔兽争霸3终极优化指南:WarcraftHelper 2024免费配置教程 【免费下载链接】WarcraftHelper Warcraft III Helper , support 1.20e, 1.24e, 1.26a, 1.27a, 1.27b 项目地址: https://gitcode.com/gh_mirrors/wa/WarcraftHelper 还在为经典游戏《魔兽争霸3》在现…...
3分钟快速上手:SillyTavern如何让你成为AI聊天高手
3分钟快速上手:SillyTavern如何让你成为AI聊天高手 【免费下载链接】SillyTavern LLM Frontend for Power Users. 项目地址: https://gitcode.com/GitHub_Trending/si/SillyTavern 你是否厌倦了千篇一律的AI对话界面?想要一个能真正理解你需求、支…...
硬件工程师的办公室布局与效率系统:从工具管理到创意激发
1. 我的“极乐之穹”:一个硬件工程师的办公室漫游每次在博客里提到“极乐之穹”,指的都是我的办公室。偶尔,我也会聊起在四处搜罗时遇到并收入囊中的那些令人心动的电子设备或“艺术品”。时间久了,总有人让我拍点照片分享。问题在…...
Arm CoreSight TPIU-M调试技术详解与应用
1. Arm CoreSight TPIU-M技术深度解析在嵌入式系统开发中,调试和追踪功能是确保系统可靠性和性能优化的关键。作为Arm CoreSight调试架构的重要组成部分,TPIU-M(Trace Port Interface Unit for Cortex-M)为Cortex-M系列处理器提供…...
