尧图网络 高端网站定制 · 原创设计
免费咨询热线
400-888-6620
免费获取方案
推荐题目:洛谷 P3995 树链剖分
推荐题目洛谷P3995 树链剖分题目背景树链剖分计算机术语指一种对树进行划分的算法它先通过轻重边剖分将树分为多条链保证每个点属于且只属于一条链然后再通过数据结构树状数组、SBT、SPLAY、线段树等来维护每一条链。(摘自百度百科)题目描述大宁最近在研究树链剖分。他发现树链剖分的时间复杂度主要由轻重链的划分方式保证最常见的剖分方式是按照子树大小剖分。如图摘自百度百科黑边为重链长度任意白边为轻链长度全部为1。注意下图 1-2, 1-3 为不同轻链。其中对于每个节点其在重链上的儿子叫做重儿子且只有唯一一个而叶子节点没有重儿子。例如对于图上 1 号点重儿子是 4 号点。显然对于不同剖分方式同一组查询访问的链的数量不同。现在给定一棵根为 1 号节点的有根树和若干询问操作每次询问访问从u uu到v vv上面的所有轻重链一次。例如在上图的剖分方式中查询 3 到 8 一共访问了 3 条轻链 1-3重链 1-4轻链 4-8查询 3 到 11 一共访问了 3 条轻链 1-3轻链 1-2重链 2-11。大宁请你给出一种剖分方案使所有询问操作总共访问的轻重链总条数最小由于可能有许多合法方案请任意输出一种我们提供Special Judge检验你的方案的正确性。设你的剖分方式的查询链数为x xxstd 答案的查询数为x 0 x_0x0​评分参数为a aa。你得到的分数是10 1010分 当x ≤ x 0 x\leq x_0x≤x0​。8 88分 当0 ( x − x 0 ) ≤ a 0(x-x_0)\leq a0(x−x0​)≤a。7 77分 当a ( x − x 0 ) ≤ 2 × a a(x-x0)\leq 2\times aa(x−x0)≤2×a。6 66分 当2 × a ( x − x 0 ) ≤ 3 × a 2\times a(x-x0)\leq 3\times a2×a(x−x0)≤3×a。1 11分 输出了合法的方案。a ⌊ q 300 ⌋ a\lfloor\frac{q}{300}\rfloora⌊300q​⌋,q qq为询问总数。我们提供了Div\_Checker.exe来检验你的答案。把它放到div.in,div.out同文件夹下运行其中div.in是输入数据的文件形式,div.out是你的程序在该输入下的输出。如果你的div.out答案合法它会返回Your answer is XXX.XXX是你的剖分方式在该输入数据下的查询次数否则返回Wrong Outdata.注意: 在正式提交的时候不能使用文件输入输出。输入格式第一行有两个正整数n nn和q qq表示该树的节点数n nn和查询次数q qq。接下来n − 1 n-1n−1行各有两个正整数u uuv vv表示u uu和v vv之间有一条边。接下来q qq行为q qq个询问为U UUV VV表示有一次从U UU到V VV的询问。输出格式一共n nn行对于i ii号节点如果它不是叶子节点那么输出它在你的剖分方案里的重儿子否则输出 0。输入输出样例 #1输入 #114 7 1 4 4 10 4 9 4 8 9 13 13 14 3 1 7 3 2 1 2 6 6 12 11 6 5 2 11 3 7 8 2 8 11 1 8 14 5 7 9 14输出 #12 6 7 8 0 11 0 0 13 0 0 0 14 0说明/提示样例即为上图但图上的剖分方式对于此处的查询并非最优。对于20 % 20\%20%的数据n , q 10 n,q10n,q10对于60 % 60\%60%的数据n , q 1000 n,q1000n,q1000对于100 % 100\%100%的数据1 n 100000 1n1000001n100000,1 q 200000 1q2000001q200000,保证给出的是一棵合法的树。Div_Checker下载如果对Checker的使用方式不太理解请参照下面的图片图中数据为样例。一个合法方案的输出。不合法方案的输出。upd 2022.8.26 \text{upd 2022.8.26}upd 2022.8.26新增加一组 Hack 数据。
RELATED

相关推荐

Arduino无线通信入门:315MHz RF Kit原理、实战与优化

Arduino无线通信入门:315MHz RF Kit原理、实战与优化

1. 项目概述:从“线”到“波”的无线通信入门如果你玩过Arduino,大概率经历过这样的场景:传感器、显示屏、电机,各种模块之间用杜邦线连得密密麻麻,稍微动一下就可能接触不良,项目稍微复杂一点,…

📅 2026/9/23 21:29:48
如何在Draw.io中通过Mermaid插件实现文本驱动的高效图表制作

如何在Draw.io中通过Mermaid插件实现文本驱动的高效图表制作

如何在Draw.io中通过Mermaid插件实现文本驱动的高效图表制作 【免费下载链接】drawio_mermaid_plugin Mermaid plugin for drawio desktop 项目地址: https://gitcode.com/gh_mirrors/dr/drawio_mermaid_plugin 在当今的技术文档和系统设计工作中,图表制作是…

📅 2026/9/23 21:29:26
微信小程序web-view业务域名配置全解析:从原理到实战避坑指南

微信小程序web-view业务域名配置全解析:从原理到实战避坑指南

1. 问题缘起:当web-view遇到“非业务域名”的拦截 做小程序开发,尤其是需要内嵌H5页面的场景, web-view 组件绝对是绕不开的利器。它让我们能在小程序这个相对封闭的生态里,灵活地展示一个功能完整的网页,无论是活动…

📅 2026/8/22 17:20:43
MORE NEWS

更多资讯

📰

Python学生成绩管理系统实战部署与避坑指南

简介:本资源是一套完整的Python学生成绩管理系统课程设计实践包,面向计算机专业初学者、课程设计学生及Python入门开发者,聚焦软件工程全流程实践,解决从需求分析到部署运行的系统开发能力训练问题。压缩包共412个文件&#xff0c…

📰

JAVA微信小程序商城源码:完整后台才是核心,从部署到改造全解析

简介:这套JAVA微信小程序商城源码附带完整后台,适合具备一定Java基础、希望快速搭建微信商城小程序的开发者或初创团队。项目采用springmvcmybatisspringmavenmysql架构,前端基于H5和CSS3,后台使用bootstrap-ace技术,整…

📰

DeepSeek多模态模型实战:从Transformer原理到微调部署

简介:围绕DeepSeek模型多模态处理与应用的深度学习技术文档,面向自然语言处理与计算机视觉方向的研究者、工程师及技术团队,系统讲解其在文本理解、图像识别和多模态信息融合方面的实现原理与落地方法。这份技术资料以单个docx文档承载&#…

📰

RDMA原子操作与Device Tracer实战:PRM第4分册避坑指南

简介:这份资源是 Mellanox 网卡编程参考手册(PRM)第 4 部分,面向从事 RDMA 驱动开发、固件调试与高性能网络协议栈实现的工程师,以及需要深入理解 HCA 硬件行为的研究人员。内容聚焦扩展原子操作、WQE 格式与 RDMA 写原…

📰

tvm.relay.nn:TVM Relay 神经网络算子库实战指南

编译器深度学习模型优化 【免费下载链接】tvm Open deep learning compiler stack for cpu, gpu and specialized accelerators 项目地址: https://gitcode.com/gh_mirrors/tvm7/tvm 点击查看 免费下载 导读 tvm.relay.nn 是 Apache TVM Relay IR 中的神经网络算子…

📰

系统接口设计对接方案:从契约设计到联调排错的完整实践

简介:系统接口设计对接方案是一份面向系统架构师、后端开发与集成工程师的接口设计文档,重点解决跨系统对接时面临的安全、标准、数据格式与运维责任划分等问题。文档以SOA体系架构为基础,系统讲解了服务目录标准(UDDI v2&#xf…

TODAY

今日更新

THIS WEEK

本周精选

THIS MONTH

本月热门

读完文章,想聊聊您的网站?

告诉我们您的行业与需求,资深顾问一对一梳理方案与报价,全程免费。

📞 💬