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

A. Copil Copac Draws Trees

Problem - 1830A - Codeforces

问题描述:

科皮尔-科帕克(Copil Copac)得到一个由 n − 1 n-1 n1条边组成的列表,该列表描述了一棵由 n n n个顶点组成的树。他决定用下面的算法来绘制它:

  • 步骤 0 0 0:绘制第一个顶点(顶点 1 1 1)。进入步骤 1 1 1
  • 步骤 1 1 1:对于输入中的每一条边,依次绘制:如果这条边连接了一个已绘制的顶点 u u u和一个未绘制的顶点 v v v,则绘制未绘制的顶点 v v v和这条边。检查完每一条边后,进入步骤 2 2 2
  • 步骤 2 2 2:如果所有顶点都绘制完毕,则终止算法。否则,转到步骤 1 1 1

读取次数定义为 Copil Copac 执行步骤 1 1 1的次数。

请计算 Copil Copac 绘制这棵树所需的读数。

插件 cf better

问题简化:建树,按建树顺序进行绘制。对于第i个边,可以向j > i的边进行绘制不消耗次数,否则需要花一次绘制。问绘制需要的次数。

思路:类似树形dp。

代码:

#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <set>
#include <map>
#include <queue>
#include <ctime>
#include <random>
#include <sstream>
#include <numeric>
#include <stdio.h>
#include <functional>
#include <bitset>
#include <algorithm>
using namespace std;#define Multiple_groups_of_examples
#define IOS std::cout.tie(0);std::cin.tie(0)->sync_with_stdio(false);
#define dbgnb(a) std::cout << #a << " = " << a << '\n';
#define dbgtt cout<<" !!!test!!! "<<endl;
#define rep(i,x,n) for(int i = x; i <= n; i++)#define all(x) (x).begin(),(x).end()
#define pb push_back
#define vf first
#define vs secondtypedef long long LL;
typedef pair<int,int> PII;const int INF = 0x3f3f3f3f;
const int N = 2e5 + 21;void inpfile();
void solve() {int n; cin>>n;vector<vector<PII>> g(n+1); // PII({ 点u,输入顺序})for(int i = 2; i <= n ; ++i) {int u,v; cin>>u>>v;// 无向 g[u].push_back({v,i});g[v].push_back({u,i});}// f[i] 表示 到结点i用了多少个次数vector<int> f(n + 1);int ans = 0; // 记录答案f[1] = 1; // 第一个节点需要一次auto vis(f); // 是否走过,走过不走,也可以不用这个vis数组,因为 y == fu || idx == fi 就已经将这个判断过了(//  当前节点  当前节点的父亲节点  这个节点的边的输入顺序编号auto dfs = [&](auto &&dfs, int u, int fu, int fi) -> void {for(auto t: g[u]) {// 得到 儿子节点 和 <u,y> 边的编号int y = t.vf, idx = t.vs;if(y == fu || idx == fi) continue;if(vis[y]) continue;vis[y] = 1;// 如果 <u,y> 的输入编号 小于 <fu,u> 的输入编号则需要消耗次数f[y] = f[u] + (idx < fi);dfs(dfs, y,u,idx);}// 更新答案,肯定最大的,因为题要求是全部绘制完需要的次数ans = max(ans, f[u]);};dfs(dfs,1,-1,0);cout<<ans<<endl;
}
int main()
{#ifdef Multiple_groups_of_examplesint T; cin>>T;while(T--)#endifsolve();return 0;
}
void inpfile() {#define mytest#ifdef mytestfreopen("ANSWER.txt", "w",stdout);#endif
}

相关文章:

A. Copil Copac Draws Trees

Problem - 1830A - Codeforces 问题描述&#xff1a; 科皮尔-科帕克&#xff08;Copil Copac&#xff09;得到一个由 n − 1 n-1 n−1条边组成的列表&#xff0c;该列表描述了一棵由 n n n个顶点组成的树。他决定用下面的算法来绘制它&#xff1a; 步骤 0 0 0&#xff1a…...

D359周赛复盘:贪心解决求最小和问题⭐⭐+较为复杂的双层线性DP⭐⭐

文章目录 2828.判别首字母缩略词完整版 2829.k-avoiding数组的最小总和&#xff08;贪心解法&#xff09;思路完整版 类似题&#xff1a;2834.找出美丽数组的最小和思路完整版 2830.销售利润最大化⭐⭐思路DP数组含义递推公式 完整版 2828.判别首字母缩略词 给你一个字符串数组…...

python基础之miniConda管理器

一、介绍 MiniConda 是一个轻量级的 Conda 版本&#xff0c;它是 Conda 的精简版&#xff0c;专注于提供基本的环境管理功能。Conda 是一个流行的开源包管理系统和环境管理器&#xff0c;用于在不同的操作系统上安装、管理和运行软件包。 与完整版的 Anaconda 相比&#xff0c…...

C++算法 —— 分治(1)快排

文章目录 1、颜色分类2、排序数组3、第k个最大的元素&#xff08;快速选择&#xff09;4、最小的k个数&#xff08;快速选择&#xff09; 分治&#xff0c;就是分而治之&#xff0c;把大问题划分成多个小问题&#xff0c;小问题再划分成更小的问题。像快排和归并排序就是分治思…...

接口用例设计

章节目录&#xff1a; 一、针对输入设计1.1 数值型1.2 字符串型1.3 数组或链表类型 二、针对业务逻辑2.1 约束条件分析2.2 操作对象分析2.3 状态转换分析2.4 时序分析 三、针对输出设计3.1 针对输出结果3.2 接口超时 四 、其他测试设计4.1 已废弃接口测试4.2 接口设计合理性分析…...

Selenium超级详细的教程

Selenium是一个用于自动化测试的工具&#xff0c;它可以模拟用户在浏览器中的各种操作。除了用于测试&#xff0c;Selenium还可以用于爬虫&#xff0c;特别是在处理动态加载页面时非常有用。本文将为您提供一个超级详细的Selenium教程&#xff0c;以帮助您快速入门并了解其各种…...

服务报network error错误

问题&#xff1a;服务请求时会偶发性的报【network error网络超时】&#xff08;请求瞬间就报&#xff09; 可能原因&#xff1a; 服务器linux内核调优时将&#xff1a;net.ipv4.tcp_tw_recycle设置为1&#xff0c;开启TCP连接中TIME-WAIT sockets的快速回收&#xff0c;默认为…...

【ES6】利用 Proxy实现函数名链式效果

利用 Proxy&#xff0c;可以将读取属性的操作&#xff08;get&#xff09;&#xff0c;转变为执行某个函数&#xff0c;从而实现属性的链式操作。 var pipe function (value) {var funcStack [];var oproxy new Proxy({} , {get : function (pipeObject, fnName) {if (fnNa…...

hive部署

下载hive安装包&#xff1a;https://dlcdn.apache.org/hive/hive-2.3.9/解压及环境部署 tar -zxvf apache-hive-2.3.9-bin.tar.gz mv apache-hive-2.3.9-bin hivevim /etc/profile添加至环境变量 export HIVE_HOME/usr/local/hive export PATH$PATH:$HIVE_HOME/binsource /etc…...

ip白名单之网段

代码托管&#xff0c;有时候为了安全性&#xff0c;限制网段内的ip可以访问。 IP地址和掩码均知道时才能确定主机所在的网段&#xff0c;也就是用这个原理来限制可访问的IP网段了。 ip后面加上“/N”就代表掩码的二进制”1“有N位。 例如&#xff1a; ①0.0.0.0/0 主机ip地…...

PMP项目管理主要学习内容是什么?

PMP项目管理是指根据美国项目管理学会(Project Management Institute&#xff0c;简称PMI)制定的项目管理知识体系和方法论进行项目管理的一种认证。PMP主要关注项目的规划、执行和控制等方面的知识和技能。 下面是PMP项目管理《PMBOK指南》第六版的主要学习内容&#xff1a; …...

小米面试题——不用加减乘除计算两数之和

前言 &#xff08;1&#xff09;刷B站看到一个面试题&#xff0c;不用加减乘除计算两数之和。 &#xff08;2&#xff09;当时我看到这个题目&#xff0c;第一反应就是感觉这是一个数电题目。不过需要采用C语言的方式编写出来。 &#xff08;3&#xff09;不过看到大佬的代码之…...

Mysql 日志管理 数据备份

MySQL日志管理 MySQL的默认日志保存位置为/usr/local/mysql/data 日志开启方式有两种&#xff1a;通过配置文件或者是通过命令 通过命令修改开启的日志是临时的&#xff0c;关闭或重启服务后就会关闭 日志的分类 1.错误日志 用来记录当MySQL启动、停止或运行时发生的错误信…...

Java小记-腾讯2020校招-后台-逛街

题目描述&#xff1a; 小Q在周末的时候和他的小伙伴来到大城市逛街&#xff0c;一条步行街上有很多高楼&#xff0c;共有n座高楼排成一行。 小Q从第一栋一直走到了最后一栋&#xff0c;小Q从来都没有见到这么多的楼&#xff0c;所以他想知道他在每栋楼的位置处能看到多少栋楼呢…...

FFmpeg5.0源码阅读——FFmpeg大体框架

摘要&#xff1a;前一段时间熟悉了下FFmpeg主流程源码实现&#xff0c;对FFmpeg的整体框架有了个大概的认识&#xff0c;因此在此做一个笔记&#xff0c;希望以比较容易理解的文字描述FFmpeg本身的结构&#xff0c;加深对FFmpeg的框架进行梳理加深理解&#xff0c;如果文章中有…...

【算法刷题之字符串篇】

目录 1.leetcode-344. 反转字符串&#xff08;1&#xff09;方法&#xff1a;双指针 2.leetcode-541. 反转字符串 II&#xff08;1&#xff09;方法一&#xff1a;模拟&#xff08;2&#xff09;方法二&#xff1a;双指针 3.leetcode-剑指 Offer 05. 替换空格&#xff08;1&…...

js中forEach和map的区别:forEach不会改变原数组,而map会改变数组?错了错了

1.提出思考&#xff1f;forEach不会改变原数组&#xff0c;而map会改变数组&#xff1f; 看到掘金上一篇文章觉得很有意思&#xff1a;大致是描述一般面试官问js中forEach和map的区别&#xff1f;都会回答forEach不会改变原数组&#xff0c;而map会改变&#xff0c;我也一直对…...

深度对话:从底层看Sui设计理念及网络规模扩展

近日&#xff0c;我们采访了George Danezis以了解Sui的交易处理系统如何促成高性能网络。他是Mysten Labs的联合创始人和首席科学家&#xff08;Sui的最初贡献者&#xff09;&#xff0c;也是伦敦大学学院&#xff08;University College London&#xff0c;UCL&#xff09;安全…...

2.单链表练习

1. 链表的基本概念 链表&#xff08;Linked List&#xff09;是一种常见的数据结构&#xff0c;用于存储一系列元素&#xff0c;这些元素可以是任意类型的数据。链表中的每个元素被称为节点&#xff08;Node&#xff09;&#xff0c;每个节点包含两部分&#xff1a;一个存储数…...

Wordpress 安装插件和主题报错

安装主题和插件的时候&#xff0c;就是这个恶心的报错&#xff0c; Wordpress plugin install: Could not create directory 这是权限惹的祸&#xff0c;如下一顿操作猛如虎&#xff0c;就解决了。 sudo chown -R www:www wp-content/themes sudo chown -R www:www wp-conte…...

蓝桥杯 2024 15届国赛 A组 儿童节快乐

P10576 [蓝桥杯 2024 国 A] 儿童节快乐 题目描述 五彩斑斓的气球在蓝天下悠然飘荡&#xff0c;轻快的音乐在耳边持续回荡&#xff0c;小朋友们手牵着手一同畅快欢笑。在这样一片安乐祥和的氛围下&#xff0c;六一来了。 今天是六一儿童节&#xff0c;小蓝老师为了让大家在节…...

大语言模型如何处理长文本?常用文本分割技术详解

为什么需要文本分割? 引言:为什么需要文本分割?一、基础文本分割方法1. 按段落分割(Paragraph Splitting)2. 按句子分割(Sentence Splitting)二、高级文本分割策略3. 重叠分割(Sliding Window)4. 递归分割(Recursive Splitting)三、生产级工具推荐5. 使用LangChain的…...

STM32标准库-DMA直接存储器存取

文章目录 一、DMA1.1简介1.2存储器映像1.3DMA框图1.4DMA基本结构1.5DMA请求1.6数据宽度与对齐1.7数据转运DMA1.8ADC扫描模式DMA 二、数据转运DMA2.1接线图2.2代码2.3相关API 一、DMA 1.1简介 DMA&#xff08;Direct Memory Access&#xff09;直接存储器存取 DMA可以提供外设…...

工程地质软件市场:发展现状、趋势与策略建议

一、引言 在工程建设领域&#xff0c;准确把握地质条件是确保项目顺利推进和安全运营的关键。工程地质软件作为处理、分析、模拟和展示工程地质数据的重要工具&#xff0c;正发挥着日益重要的作用。它凭借强大的数据处理能力、三维建模功能、空间分析工具和可视化展示手段&…...

江苏艾立泰跨国资源接力:废料变黄金的绿色供应链革命

在华东塑料包装行业面临限塑令深度调整的背景下&#xff0c;江苏艾立泰以一场跨国资源接力的创新实践&#xff0c;重新定义了绿色供应链的边界。 跨国回收网络&#xff1a;废料变黄金的全球棋局 艾立泰在欧洲、东南亚建立再生塑料回收点&#xff0c;将海外废弃包装箱通过标准…...

【HTTP三个基础问题】

面试官您好&#xff01;HTTP是超文本传输协议&#xff0c;是互联网上客户端和服务器之间传输超文本数据&#xff08;比如文字、图片、音频、视频等&#xff09;的核心协议&#xff0c;当前互联网应用最广泛的版本是HTTP1.1&#xff0c;它基于经典的C/S模型&#xff0c;也就是客…...

是否存在路径(FIFOBB算法)

题目描述 一个具有 n 个顶点e条边的无向图&#xff0c;该图顶点的编号依次为0到n-1且不存在顶点与自身相连的边。请使用FIFOBB算法编写程序&#xff0c;确定是否存在从顶点 source到顶点 destination的路径。 输入 第一行两个整数&#xff0c;分别表示n 和 e 的值&#xff08;1…...

佰力博科技与您探讨热释电测量的几种方法

热释电的测量主要涉及热释电系数的测定&#xff0c;这是表征热释电材料性能的重要参数。热释电系数的测量方法主要包括静态法、动态法和积分电荷法。其中&#xff0c;积分电荷法最为常用&#xff0c;其原理是通过测量在电容器上积累的热释电电荷&#xff0c;从而确定热释电系数…...

【JVM面试篇】高频八股汇总——类加载和类加载器

目录 1. 讲一下类加载过程&#xff1f; 2. Java创建对象的过程&#xff1f; 3. 对象的生命周期&#xff1f; 4. 类加载器有哪些&#xff1f; 5. 双亲委派模型的作用&#xff08;好处&#xff09;&#xff1f; 6. 讲一下类的加载和双亲委派原则&#xff1f; 7. 双亲委派模…...

[免费]微信小程序问卷调查系统(SpringBoot后端+Vue管理端)【论文+源码+SQL脚本】

大家好&#xff0c;我是java1234_小锋老师&#xff0c;看到一个不错的微信小程序问卷调查系统(SpringBoot后端Vue管理端)【论文源码SQL脚本】&#xff0c;分享下哈。 项目视频演示 【免费】微信小程序问卷调查系统(SpringBoot后端Vue管理端) Java毕业设计_哔哩哔哩_bilibili 项…...