[AHOI2008] 紧急集合 / 聚会

news/2024/4/15 19:02:34

[AHOI2008] 紧急集合 / 聚会

题目描述

欢乐岛上有个非常好玩的游戏,叫做“紧急集合”。在岛上分散有 n n n 个等待点,有 n − 1 n-1 n1 条道路连接着它们,每一条道路都连接某两个等待点,且通过这些道路可以走遍所有的等待点,通过道路从一个点到另一个点要花费一个游戏币。

参加游戏的人三人一组,开始的时候,所有人员均任意分散在各个等待点上(每个点同时允许多个人等待),每个人均带有足够多的游戏币(用于支付使用道路的花费)、地图(标明等待点之间道路连接的情况)以及对话机(用于和同组的成员联系)。当集合号吹响后,每组成员之间迅速联系,了解到自己组所有成员所在的等待点后,迅速在 n n n 个等待点中确定一个集结点,组内所有成员将在该集合点集合,集合所用花费最少的组将是游戏的赢家。

小可可和他的朋友邀请你一起参加这个游戏,由你来选择集合点,聪明的你能够完成这个任务,帮助小可可赢得游戏吗?

输入格式

第一行两个正整数 n n n m m m,分别表示等待点的个数(等待点也从 1 1 1 n n n 进行编号)和获奖所需要完成集合的次数。

随后 n − 1 n-1 n1 行,每行两个正整数 a , b a,b a,b,表示编号为 a a a 和编号为 b b b 的等待点之间有一条路。

随后 m m m 行,每行用三个正整数 x , y , z x,y,z x,y,z,表示某次集合前小可可、小可可的朋友以及你所在等待点的编号。

输出格式

输出共 m m m 行,每行两个用空格隔开的整数 p , c p,c p,c。其中第 i i i 行表示第 i i i 次集合点选择在编号为 p p p 的等待点,集合总共的花费是 c c c 个游戏币。

样例 #1

样例输入 #1

6 4  
1 2  
2 3  
2 4 
4 5
5 6
4 5 6
6 3 1
2 4 4 
6 6 6

样例输出 #1

5 2
2 5
4 1
6 0

提示

对于 40 % 40\% 40% 的数据, n ≤ 2 × 1 0 3 n\leq2\times10^3 n2×103 m ≤ 2 × 1 0 3 m\leq2\times 10^3 m2×103

对于 100 % 100\% 100% 的数据, 1 ≤ x , y , z ≤ n ≤ 5 × 1 0 5 1\leq x,y,z\leq n\leq 5\times10^5 1x,y,zn5×105 1 ≤ m ≤ 5 × 1 0 5 1\leq m\leq 5\times 10^5 1m5×105

分析

LCA与树的分析,由于题目中已经保证了是树,而有三个标记点,每次求任意两个的LCA,而必定有两个相同,即可得到一个最近的LCA,在建树时求出深度,用O(1)求出最近点的距离

代码

#include <bits/stdc++.h>
using namespace std;
const int M=6*1e5;
vector<int > T[M];
int n,m,s;
struct LCA{static const int k=25;int f[M][k+1],d[M],dmax=0;void init(int s){f[s][0]=s;for(int i=1;(1<<i)<=dmax;i++)for(int j=1;j<=n;j++)f[j][i]=f[f[j][i-1]][i-1];return;}int query(int x,int y){if(d[x]>d[y]) swap(x,y);for(int i=k;i>=0;i--) if(d[f[y][i]]>=d[x]) y=f[y][i];if(x==y) return x;for(int i=k;i>=0;i--){if(f[x][i]!=f[y][i])x=f[x][i],y=f[y][i];}return f[x][0];}void dfs(int u,int fa,int dep){if(d[u]) return;d[u]=dep;f[u][0]=fa;for(auto& v:T[u]) {dfs(v,u,dep+1);}dmax=max(dmax,dep);return;}void finit(int s){memset(f,0,sizeof(f));memset(d,0,sizeof(d));dfs(s,s,1);init(s);}
}solve;
signed main(){ios::sync_with_stdio(false);cin>>n>>m;for(int i=1,u,v;i<n;i++){cin>>u>>v;T[u].push_back(v);T[v].push_back(u);}solve.finit(1);for(int i=1,a,b,c;i<=m;i++){cin>>a>>b>>c;int x1=solve.query(a,b),x2=solve.query(b,c),x3=solve.query(a,c);if (x1==x2){int ans=abs(solve.d[x3]-solve.d[a])+abs(solve.d[x3]-solve.d[c]);ans+=abs(solve.d[x1]-solve.d[b])+abs(solve.d[x1]-solve.d[x3]);cout<<x3<<' '<<ans<<endl;}else if(x1==x3){int ans=abs(solve.d[x2]-solve.d[c])+abs(solve.d[x2]-solve.d[b]);ans+=abs(solve.d[x3]-solve.d[a])+abs(solve.d[x3]-solve.d[x2]);cout<<x2<<' '<<ans<<endl;}else{int ans=abs(solve.d[x1]-solve.d[a])+abs(solve.d[x1]-solve.d[b]);ans+=abs(solve.d[x2]-solve.d[c])+abs(solve.d[x2]-solve.d[x1]);cout<<x1<<' '<<ans<<endl;}}return 0;
}

http://www.ppmy.cn/news/1342672.html

相关文章

Java JDBC 增删改查

数据库连接 import java.sql.Connection; import java.sql.DriverManager; import java.sql.PreparedStatement; import java.sql.ResultSet; import java.sql.SQLException; import java.sql.Statement;Connection con;// 声明数据库连接对象String url "jdbc:mysql://…

查看自己电脑是arm还是x64(x86);linux操作系统识别

1、查看自己电脑是arm还是x64&#xff08;x86&#xff09; linux 参考&#xff1a; https://liuweiqing.blog.csdn.net/article/details/131783851 uname -a如果输出是 x86_64&#xff0c;那么你的系统是 64 位的 x86 架构&#xff08;通常我们称之为 x64&#xff09;。如果…

Unity引擎学习笔记之【动画、动画器操作】

动画Animate Animation是基于关键帧的动画系统&#xff0c;适用于简单的动画需求&#xff1b; 而Animator是一种状态机驱动的动画系统&#xff0c;适用于更复杂的动画逻辑和交互式动画。 通常&#xff0c;Animator组件更适合用于游戏中的角色动画控制&#xff0c; 而Animation…

【Vue】3-1、Vue 3 简介

一、Vue 3 的优势 Vue 2 Options API 的缺陷&#xff1a; 一个功能往往需要在不同的 vue 配置项中定义属性和方法&#xff0c;比较分散&#xff0c;需求简单还好&#xff0c;清晰明了&#xff1b;但是需求复杂之后&#xff0c;就会多出 watch&#xff0c;computed&#xff0c;i…

【lesson40】理解文件系统

文章目录 问题磁盘结构&#xff08;物理&#xff09;磁盘的存储结构磁盘的抽象结构 问题 1.有没有没有被打开的文件&#xff1f;当然有 在哪里呢&#xff1f;磁盘中也叫磁盘级文件 2.学习磁盘级别文件的侧重点在哪&#xff1f; 站在单个文件角度: 这个文件在哪里&#xff1f…

Stable Diffusion 模型下载:国风3 GuoFeng3

文章目录 模型介绍生成案例案例一案例二案例三案例四案例五案例六案例七案例八案例九案例十推荐提示词下载地址模型介绍 欢迎使用GuoFeng3模型 - 这是一个中国华丽古风风格模型,也可以说是一个古风游戏角色模型,具有2.5D的质感。 条目内

657.机器人能否返回原点(Java)

题目描述 在二维平面上&#xff0c;有一个机器人从原点 (0, 0) 开始。给出它的移动顺序&#xff0c;判断这个机器人在完成移动后是否在 (0, 0) 处结束。 移动顺序由字符串 moves 表示。字符 move[i] 表示其第 i 次移动。机器人的有效动作有 R&#xff08;右&#xff09;&#x…

【安装指南】nodejs下载、安装与配置详细教程

目录 &#x1f33c;一、概述 &#x1f340;二、下载node.js &#x1f337;三、安装node.js &#x1f341;四、配置node.js &#x1f33c;一、概述 Node.js 是一个基于 Chrome V8 引擎的 JavaScript 运行时&#xff0c;用于构建可扩展的网络应用程序。Node.js 使用事件驱动、…

Java基础 集合(二)List详解

目录 简介 数组与集合的区别如下&#xff1a; 介绍 AbstractList 和 AbstractSequentialList Vector 替代方案 Stack ArrayList LinkedList 前言-与正文无关 生活远不止眼前的苦劳与奔波&#xff0c;它还充满了无数值得我们去体验和珍惜的美好事物。在这个快节奏的世界…

Vue组件通信讲解[父子组件通信]

Vue组件通信讲解 在Vue中&#xff0c;父子组件之间的通信可以通过props和emit来实现。props用于从父组件向子组件传递数据&#xff0c;而$emit用于从子组件向父组件触发事件。 以下是一个包含子传父和父传子通信的Vue案例解决方案&#xff1a; 父组件&#xff1a;Parent.vue…

【数据结构】快速排序,基数排序/桶排序

基数排列 &#xff1a; 桶排序&#xff1a;低位优先&#xff0c;所有数据从&#xff08;个位&#xff09;开始 依次放入10个桶内&#xff08;入队&#xff0c;再从桶里取出&#xff0c;直到完全有序&#xff09;。 基数&#xff08;桶&#xff09;排序&#xff1a;低位优先&am…

算法总结归纳(第十一天)(部分数据结构、图论(部分))

目录 一、trie树 题目描述&#xff1a; 输入格式 输出格式 输入样例&#xff1a; 输出样例&#xff1a; ①、思路 ②、代码实现 二、并查集 1、样例 题目描述&#xff1a; 输入格式 输出格式 输入样例&#xff1a; 输出样例&#xff1a; ①、思路 ②、代码实现…

DHCP简介

定义 动态主机配置协议DHCP&#xff08;Dynamic Host Configuration Protocol&#xff09;是一种用于集中对用户IP地址进行动态管理和配置的技术。即使规模较小的网络&#xff0c;通过DHCP也可以使后续增加网络设备变得简单快捷。 DHCP是在BOOTP&#xff08;BOOTstrap Protoc…

Python语言的特点及使用技巧

Python语言以其简洁、清晰的语法和强大的功能而闻名&#xff0c;其特点和使用技巧包括但不限于以下几个方面&#xff1a; 特点&#xff1a; 易读易写&#xff1a;Python强调代码的可读性和简洁性&#xff0c;使用空格缩进代替花括号来组织代码块&#xff0c;使得代码结构清晰。…

C++集群聊天服务器 网络模块+业务模块+CMake构建项目 笔记 (上)

跟着施磊老师做C项目&#xff0c;施磊老师_腾讯课堂 (qq.com) 一、网络模块ChatServer chatserver.hpp #ifndef CHATSERVER_H #define CHATSERVER_H#include <muduo/net/TcpServer.h> #include <muduo/net/EventLoop.h> using namespace muduo; using namespace …

MySQL运维实战(5.3) MySQL数据乱码的一些情况

作者&#xff1a;俊达 表数据乱码 表数据出现乱码的情况通常是由于数据的真实编码与相关参数不一致引起的&#xff0c;其中包括常见的参数如character_set_client、character_set_results、字段编码以及终端编码等。确保这些参数保持一致&#xff0c;可以有效预防和解决乱码问…

List的模拟实现 迭代器

———————————————————— list与vector相比&#xff0c;插入、删除等操作实现的成本非常低&#xff0c;如果在C语言阶段熟悉理解过链表&#xff0c;那么现在实现起来list就显得比较简单&#xff0c;可以说操作层面上比vector更简洁&#xff0c;因为list没有扩…

ElementUI Form:Select 选择器

ElementUI安装与使用指南 Select 选择器 点击下载learnelementuispringboot项目源码 效果图 el-select.vue&#xff08;Select选择器&#xff09;页面效果图 项目里el-select.vue代码 <script> export default {name: el_select,data() {return {options: [{value…

Redis -- String 字符串, 计数命令,字符串操作

"学如逆水行舟&#xff0c;不进则退。" 目录 Redis的String字符串 常见命令 set get mget mset setnx setex psetex 计数命令 incr incrby decr decrby incrbyfloat 字符串操作 append getrange setrange strlen 小结 string内部编码 Redis…

C语言---—————— 快速创建指定个数的文件

项目介绍: 这是一个简单的C语言程序,旨在根据用户输入的数字创建指定数量的文本文件。这个程序的主要功能和特点如下: 用户友好:程序首先提示用户输入要创建的txt文件的个数,使用户能够明确了解下一步的操作。文件命名策略:在每次循环中,程序会根据当前的循环计数器生成…
最新文章