HDU 5927 Auxiliary Set
原题链接:
https://acm.hdu.edu.cn/showproblem.php?pid=5927
题意:
有一颗根节点是1的树,其中有重要的点和不重要的点,重要的点需满足以下两个条件至少一个:
1.本来就是重要的点
2.是两个重要的点的最近共同祖先
有t个测试实例,对于每个测试实例:
给出结点个数n和询问次数q
对于每次询问:
给出一个数con,表示不重要的点的个数
接下来con个数是不重要的点的编号
对于每个询问,求出重要的点的个数(每次询问之间相互独立)
思路:
ans记录重要结点的个数
本来就是重要的点有n-con个
那么我们就需要检查一下不重要的点,对于每个不重要的点看看他是不是两个重要的点的最近共同祖先
对于点u,如果他的以儿子结点为根的子树中,多于两个子树里有
重要的结点,那么u就能变成重要的结点
那么我们可以先预处理好每个结点的儿子结点的个数,每个点的父节点和每个点的深度
然后再对不重要的结点按照深度从大到小的顺序排序
从最深的结点u开始遍历,如果u的有重要点的儿子结点数量超过两个,那么u就可以变成重要结点,ans++
如果变不了重要结点,说明u的有重要点的儿子结点数量要么是0要么是1,如果是0,那么u的父节点的有重要儿子结点的数量就需要-1,因为每次询问独立,那么我们需要将减掉的点给记录一下,当这次询问完毕时再复原加上
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
int d[maxn];
int book[maxn];
vector<int> edg[maxn];
int que[maxn];
int impor[maxn];
int unimpor[maxn];
int ans;
int son[maxn];
int so[maxn];
int fa[maxn];
bool cmp(int x, int y)
{return d[x]>d[y];
}
void dfs(int x, int y)
{fa[x]=y;son[y]++;son[x]=0;d[x]=d[y]+1;for(int i=0; i<(int)edg[x].size(); i++){if(edg[x][i]!=y)dfs(edg[x][i],x);}return;
}
int main()
{int t;cin>>t;int e=1; while(t--){int n;int q;scanf("%d%d", &n, &q);int i, j, x, y;for(i=0; i<n-1; i++){scanf("%d %d", &x, &y);edg[x].push_back(y);edg[y].push_back(x); }dfs(1,0);int m;printf("Case #%d:\n", e++); while(q--){scanf("%d", &m);for(i=0; i<m; i++){ scanf("%d", &unimpor[i]);//不重要节点so[unimpor[i]]=son[unimpor[i]];//节点的儿子}ans=n-m;sort(unimpor, unimpor+m, cmp);for(i=0; i<m; i++){if(so[unimpor[i]]>=2)ans++;else{if(so[unimpor[i]]==0) so[fa[unimpor[i]]]--;}}printf("%d\n", ans);}for(i=1; i<=n; i++){edg[i].clear();
// vector<int>().swap(edg[i]);}}
}相关文章:
HDU 5927 Auxiliary Set
原题链接: https://acm.hdu.edu.cn/showproblem.php?pid5927 题意: 有一颗根节点是1的树,其中有重要的点和不重要的点,重要的点需满足以下两个条件至少一个: 1.本来就是重要的点 2.是两个重要的点的最近共同祖先 有t…...
24:若所有参数皆需类型转换,请为此采用non-member函数
令class支持隐式类型转换通常是个糟糕的主意。 这条规则有其例外,最常见的例外是在建立数值类型时。 例,假设你设计一个class用来表现有理数,则允许整数“隐式转换”为有理数就很合理。 class Rational{ public:Rational(int numerator0,i…...
CMake(2)-详解-编译-安装-支持GDB-添加环境检查-添加版本号-生成安装包
目录 1.什么是CMake 1.1 编译流程CMakeLists.txt a) 最简单 demo1 b) 常用demo2 c) 单目录,源文件-输出文件 DIR_SRCS中 d)多目录,多源文件 1.2.执行命令: 1.3.自定义编译选项 2.安装和测试 3.支持GDB 4.添加环境检查 5.添加…...
java面试题(redis)
目录 1.redis主要消耗什么物理资源? 2.单线程为什么快 3.为什么要使用Redis 4.简述redis事务实现 5.redis缓存读写策略 6.redis除了做缓存,还能做些什么? 7.redis主从复制的原理 8.Redis有哪些数据结构?分别有哪些典型的应…...
Vue组件懒加载
组件懒加载 前言 组件懒加载最常用于异步加载大型/复杂组件或在需要时才进行加载 Vue 2和Vue 3均支持组件懒加载,本文将介绍如何在Vue 2和Vue 3中实现组件懒加载,和一些使用场景 1️⃣方法一:使用Webpack的代码分割能力 Vue 2和Vue 3都可以…...
Qt音视频开发42-网络推流(视频推流/本地摄像头推流/桌面推流/网络摄像头转发推流等)
一、前言 上次实现的文件推流,尽管优点很多,但是只能对现在存在的生成好的音视频文件推流,而现在更多的场景是需要将实时的视频流重新推流分发,用户在很多设备比如手机/平板/网页/电脑/服务器上观看,这样就可以很方便…...
更简单的存取Bean方式-@Bean方法注解
1.Bean方法存储 类注解是添加在某个类上的,那么方法注解是添加在某个方法前的 public class UserBeans {Beanpublic User user1(){User user new User();user.setUid(001);user.setUname("zhangsan");user.setAge(19);user.setPassword("123123");retur…...
边缘计算与AI布署应用电力物联网解决方案-RK3588开发平台
电力行业拥有规模庞大的各类设备,如电表、各类保护、采集、控制设备。面对分布式发电、储能、用户微网等一系列综合问题,边缘计算与AI布署可满足“端侧本地化”高效运用的需求,协助提升最后一公里运行效率。 瑞芯微RK3588J、内置独立NPU&…...
centos部署unity accelerator
参考 https://docs.unity3d.com/Manual/UnityAccelerator.html 方案1:下载Unity Accelerator 手动安装, unity-accelerator-app-v1.0.941g6b39b61.AppImage为下载的文件 1、放入服务器目录, chmod x unity-accelerator-app-v1.0.941g6b39b61.AppImage 2…...
HANA开发指南
建模方面 1、建模方式:图像化建模、SQL建模、CE语言建模 2、维护:SQL和CE比图形化建模更容易维护和修改 3、性能:图形化和CE会经过系统优化,性能一般优于SQL语言 4、可按需要设置参数、变量、Hierachy、聚合类型等 5、在S4系…...
请问你见过吐代码的泡泡吗(冒泡排序)
🤩本文作者:大家好,我是paperjie,感谢你阅读本文,欢迎一建三连哦。 🥰内容专栏:这里是《算法详解》,笔者用重金(时间和精力)打造,将算法知识一网打尽,希望可以…...
【VM服务管家】VM4.0平台SDK_2.1环境配置类
目录 2.1.1 环境配置:CSharp二次开发环境配置方法2.1.2 环境配置:Qt二次开发环境配置方法2.1.3 环境配置:MFC二次开发环境配置方法2.1.4 环境配置:VB.Net二次开发环境配置方法2.1.5 环境配置:运行出现Vm.Core.Solution…...
最新研究:可审计的具有拜占庭鲁棒的联邦学习方案
Y. Liang, Y. Li and B. -S. Shin, “Auditable Federated Learning With Byzantine Robustness,” in IEEE Transactions on Computational Social Systems, doi: 10.1109/TCSS.2023.3266019. 可免费下载:https://download.csdn.net/download/liangyihuai/87727720…...
JDK1.8下载、安装和环境配置教程
🎉🎉🎉点进来你就是我的人了博主主页:🙈🙈🙈戳一戳,欢迎大佬指点! 欢迎志同道合的朋友一起加油喔🦾🦾 目录 window系统安装java 下载JDK 配置环境变量 …...
天津超算,青索帮助文档
连接 第一步,点击 配置VPN(切换到局域网用)和机器(也就是各套超算系统)。 第二步,点击 机器 选择对应的机器。通常会在下方显示可用的机器,单击其中一个即可。如果只有一个机器,…...
SpringMVC的拦截器和异常处理器
目录 lerInterceptor 拦截器 1、拦截器的作用 2、拦截器的创建 3、拦截器的三个抽象方法 4、拦截器的配置 5、多个拦截器的执行顺序 SpringMVC的异常处理器 1、异常处理器概述 2、基于配置文件的异常处理 3、基于注解的异常处理 lerInterceptor 拦截器 1、拦截器的作…...
查看库文件是32位还是64位|查看lib是静态库还是导入库|判断是debug模式还是release模式
文章目录 dll位数查看lib位数查看查看lib库是静态库还是导入库dll库文件信息查看lib库文件内容查看dll库查看编译模式是debug还是release方法一方法二方法三 lib静态库查看编译模式是debug还是release方法一方法二 lib导入库查看编译模式是debug还是release查看Linux下的.a库&a…...
Python小姿势 - Python爬取数据的库——Scrapy
Python爬取数据的库——Scrapy 一、爬虫的基本原理 爬虫的基本原理就是模拟人的行为,使用指定的工具和方法访问网站,然后把网站上的内容抓取到本地来。 爬虫的基本步骤: 1、获取URL地址: 2、发送请求获取网页源码; 3、…...
[C++初阶]栈和队列_优先级队列的模拟实现 deque类 的理解
为了更好的理解优先级队列priority_queue,这里会同时进行栈和队列的提及 文章目录 简要概念(栈和队列)栈和队列的模拟实现与使用stack(栈)deque的理解和操作queue priority_queue(优先级队列)框…...
Spring是什么?关于Spring家族
初识Spring 什么是Spring? Spring是一个开源的Java企业级应用程序开发框架,由Rod Johnson于2003年创建,并在接下来的几年里得到了广泛的发展和应用。它提供了一系列面向对象的编程和配置模型,支持开发各种类型的应用程序&#x…...
RestClient
什么是RestClient RestClient 是 Elasticsearch 官方提供的 Java 低级 REST 客户端,它允许HTTP与Elasticsearch 集群通信,而无需处理 JSON 序列化/反序列化等底层细节。它是 Elasticsearch Java API 客户端的基础。 RestClient 主要特点 轻量级ÿ…...
python打卡day49
知识点回顾: 通道注意力模块复习空间注意力模块CBAM的定义 作业:尝试对今天的模型检查参数数目,并用tensorboard查看训练过程 import torch import torch.nn as nn# 定义通道注意力 class ChannelAttention(nn.Module):def __init__(self,…...
【人工智能】神经网络的优化器optimizer(二):Adagrad自适应学习率优化器
一.自适应梯度算法Adagrad概述 Adagrad(Adaptive Gradient Algorithm)是一种自适应学习率的优化算法,由Duchi等人在2011年提出。其核心思想是针对不同参数自动调整学习率,适合处理稀疏数据和不同参数梯度差异较大的场景。Adagrad通…...
【论文笔记】若干矿井粉尘检测算法概述
总的来说,传统机器学习、传统机器学习与深度学习的结合、LSTM等算法所需要的数据集来源于矿井传感器测量的粉尘浓度,通过建立回归模型来预测未来矿井的粉尘浓度。传统机器学习算法性能易受数据中极端值的影响。YOLO等计算机视觉算法所需要的数据集来源于…...
论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(一)
宇树机器人多姿态起立控制强化学习框架论文解析 论文解读:交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(一) 论文解读:交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化…...
听写流程自动化实践,轻量级教育辅助
随着智能教育工具的发展,越来越多的传统学习方式正在被数字化、自动化所优化。听写作为语文、英语等学科中重要的基础训练形式,也迎来了更高效的解决方案。 这是一款轻量但功能强大的听写辅助工具。它是基于本地词库与可选在线语音引擎构建,…...
用机器学习破解新能源领域的“弃风”难题
音乐发烧友深有体会,玩音乐的本质就是玩电网。火电声音偏暖,水电偏冷,风电偏空旷。至于太阳能发的电,则略显朦胧和单薄。 不知你是否有感觉,近两年家里的音响声音越来越冷,听起来越来越单薄? —…...
SiFli 52把Imagie图片,Font字体资源放在指定位置,编译成指定img.bin和font.bin的问题
分区配置 (ptab.json) img 属性介绍: img 属性指定分区存放的 image 名称,指定的 image 名称必须是当前工程生成的 binary 。 如果 binary 有多个文件,则以 proj_name:binary_name 格式指定文件名, proj_name 为工程 名&…...
人机融合智能 | “人智交互”跨学科新领域
本文系统地提出基于“以人为中心AI(HCAI)”理念的人-人工智能交互(人智交互)这一跨学科新领域及框架,定义人智交互领域的理念、基本理论和关键问题、方法、开发流程和参与团队等,阐述提出人智交互新领域的意义。然后,提出人智交互研究的三种新范式取向以及它们的意义。最后,总结…...
JavaScript 数据类型详解
JavaScript 数据类型详解 JavaScript 数据类型分为 原始类型(Primitive) 和 对象类型(Object) 两大类,共 8 种(ES11): 一、原始类型(7种) 1. undefined 定…...
