见面礼——图论
给定一个 n 个点 n 条边的无向图,你需要求有多少种选择图上的一个点 p 和一条边 (x,y) 的方案,使得删去 (x,y) 后图变成一棵树,且这棵树以 p 为根时每个节点的儿子个数均不超过 3。保证至少存在一种这样的方案。
Input
输入的第一行一个整数 n(2≤n≤105) 表示节点数,接下来 n 行每行两个整数 x,y(1≤x,y≤n) 描述图上的一条边。保证图中没有重边自环。
Output
输出一行一个正整数表示答案。
Input
6
1 2
1 3
1 4
1 5
1 6
2 3
Output
10
解析:
n个点n条边,所以该图就成一个环。只有将环中的一条边删去,该图才能变为一棵树。
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
typedef pair<int,int> PII;
const int N=2e6+10;
vector <int> g[N];
map <int,int> k;
int p[N];
int d[N];
bool vis[N];
vector <PII> q; //储存成环的边
int n;
void dfs(int u,int pa)
{p[u]=pa;vis[u]=1;for (auto v:g[u]){if (v==pa) continue;if (vis[v]==1&&q.size()==0) //当点 v 被再次遍历时,现在已经建成一个环了,就可以回溯将环中的每条边放入队列 q 中{q.push_back({u,v});while (p[u]!=v){q.push_back({u,p[u]});u=p[u];}q.push_back({u,p[u]});}if (vis[v]==1) continue; //走过的点,不用继续操作了,否则会死循环dfs(v,u);}
}
signed main()
{ios;cin>>n;for (int i=1;i<=n;i++){int u,v;cin>>u>>v;g[u].push_back(v);g[v].push_back(u);d[u]++;d[v]++;}for (int i=1;i<=n;i++){k[d[i]]++; //记录度数相同的点的数量}//for (auto x:k) cout<<x.first<<" "<<x.second<<endl;dfs(1,0);//for (auto x:q) cout<<x.first<<" "<<x.second<<endl;int ans=0;for (auto x:q) //遍历每条要删掉的边{int du=d[x.first];int dv=d[x.second];k[du]--;k[dv]--;k[du-1]++;k[dv-1]++;int res=0;bool flag=0;for (auto y:k) //删除边后,再遍历每个点,判断能否成为根节点{int cnt=y.first;int s=y.second;if (cnt<=3) res +=s;if (cnt>=5&&s>0) flag=1; //既当不了根节点,也当不了儿子节点}if (flag==0) ans +=res;k[du]++; //还原k[dv]++;k[du-1]--;k[dv-1]--;}cout<<ans;return 0;
}
相关文章:
见面礼——图论
给定一个 n 个点 n 条边的无向图,你需要求有多少种选择图上的一个点 p 和一条边 (x,y) 的方案,使得删去 (x,y) 后图变成一棵树,且这棵树以 p 为根时每个节点的儿子个数均不超过 3。保证至少存在一种这样的方案。 Input 输入的第一行一个整数…...
【论文阅读】SPARK:针对视觉跟踪的空间感知在线增量攻击
SPARK: Spatial-Aware Online Incremental Attack Against Visual Tracking introduction 在本文中,我们确定了视觉跟踪对抗性攻击的一个新任务:在线生成难以察觉的扰动,误导跟踪器沿着不正确的(无目标攻击,UA&#x…...
MR混合现实教学系统在汽车检修与维护课堂教学中的应用
传统的汽车检修与维护课堂教学主要依赖教师口头讲解和黑板演示,这种方式存在一定的局限性。首先,对于一些复杂的机械结构和操作过程,教师难以生动形象地展示给学生。其次,学生无法直接观察到实际操作中的细节和注意事项࿰…...
CentOS7安装xvfb,解决服务器没有X-Server的问题
Linux服务器上一般没有图形界面,但是有时候有些软件又需要图形界面.比如oracle,自动化测试(puppeteer).运行的时候会提示没有没有X服务. 这时候一般不会去特地装图形界面.这个时候就要用xvfb来创建虚拟图形窗口. xvfb介绍 Xvfb(X Virtual Frame Buffer)是基于X Window的虚拟服…...
快速集成Skywalking 9(Windows系统、JavaAgent、Logback)
目录 一、Skywalking简介二、下载Skywalking服务端三、安装Skywalking服务端3.1 解压安装包3.2 启动Skywalking 四、关于Skywalking服务端更多配置五、Java应用集成skywalking-agent.jar5.1 下载SkyWalking Java Agent5.2 集成JavaAgent5.3 Logback集成Skywalking5.4 集成效果 …...
起立科技(起鸿)在第25届高交会上展示透明OLED技术创新
第二十五届中国国际高新技术成果交易会 日期:2023年11月15日 地点:福田会展中心7号馆 深圳,2023年11月15日 — 起鸿科技,作为透明OLED领域的引领者,于今日参展了第二十五届中国国际高新技术成果交易会。这一展会将汇…...
大模型LLM 在线量化;GPTQ\AWQ量化
1、大模型LLM 在线量化 参考:https://www.cnblogs.com/bruceleely/p/17348782.html ##8bit model = AutoModel.from_pretrained("THUDM/chatglm-6b", trust_remote_code=True).quantize(8).half(...
记一次线上bug排查-----SpringCloud Gateway组件 请求头accept-encoding导致响应结果乱码
基于公司的业务需求,在SpringCloud Gateway组件的基础上,写了一个转发服务,测试开发阶段运行正常,并实现初步使用。但三个月后,PostMan请求接口,返回异常,经排查,从日志中获取到转发…...
复杂数据统计与R语言程序设计实验一
1.下载并安装R语言软件,熟悉基本操作的命令及操作界面,掌握软件的使用方法(提供学号加姓名的截图)。 2.下载并安装Rstudio, (提供运行代码及运行结果的截图)。 3.下载并安装R包DT,…...
UEFI实战——键盘操作
一、键盘操作 UEFI下如何获取键盘键值,用户输入按键方式分两种:一种是单个按键,另外一种是组合按键。两种方式对应两个Protocol服务,接下来分步讲解。 二、单个按键 单个按键使用Protocol服务是EFI_SIMPLE_TEXT_INPUT_PROTOCOL,它定义在MdePkg/Include/Protocol/Simple…...
苹果CMS首涂第30套可装修DIY主题模板免授权版
这是一款可以装修的主题,类似淘宝店装修一样,可以针对首页、栏目页、详情页、播放页进行自定义装修,内置10个模块自由选择、添加、修改、删除、排序操作,后续升级还会增加更多实用和个性模块供选择,主题内包含的导航、…...
C#每天复习一个重要小知识day2:有参与无参构造函数
using System;public class MyClass {private int value;// 有参构造函数public MyClass(int v){this.value v;}// 无参构造函数public MyClass(){this.value 0;}public static void Main(string[] args){// 使用有参构造函数实例化对象MyClass obj1 new MyClass(10);Consol…...
大语言模型的三阶段训练
为了训练专有领域模型,选择LLaMA2-7B作为基座模型,由于LLaMA模型中文词表有限,因此首先进行中文词表的扩展,然后进行三阶段训练(增量预训练,有监督微调,强化学习)。 代码将全部上传…...
面试题c/c++ --STL 算法与数据结构
1.6 STL 模板 模板底层实现:编译器会对函数模板进行两次编译, 在声明的地方对模板代码本身进行编译, 在调用的地方对参数替换后的代码进行编译。 模板传参分析 模板重载 vector 是动态空间, 随着元素的加入, 它的内…...
云原生微服务-理论篇
文章目录 分布式应用的需求分布式架构治理模式演进ESB 是什么?微服务架构 MSA微服务实践细节微服务治理框架sidercar 什么是service mesh?康威定律微服务的扩展性什么是MSA 架构?中台战略和微服务微服务总体架构组件微服务网关服务发现与路由…...
Unity模拟薄膜干涉效果
Unity制作薄膜干涉效果,色彩斑斓的黑色石头 大家好,我是阿赵。 这次来做一个模拟薄膜干涉的彩色效果,Shader是使用ASE来连接,也算是ASE做复杂一点的效果的一个例子吧。 一、什么是薄膜干涉 以下解释来源于百度百科࿱…...
AIGC ChatGPT4对Gbase数据库进行总结
ChatGPT4 用一个Prompt完成Gbase数据库的总结。 AIGC ChatGPT 职场案例 AI 绘画 与 短视频制作 PowerBI 商业智能 68集 数据库Mysql 8.0 54集 数据库Oracle 21C 142集 Office 2021实战应用 Python 数据分析实战, ETL Informatica 数据仓库案例实战 Excel 2021实操 …...
OSI网络模型与TCP/IP协议
OSI, Open system Interconnection Reference Model 开放式系统互联通信参考模型。是国际标准化组织在1984年定义的一个概念框架,用于协调制定进程间通信标准。OSI作为一个协议规范集,定义了七个层次,包括层次之间的相互关系及各层…...
C语言的5个内存段你了解吗?( 代码段/数据段/栈/堆)
前言:这些内存段在程序运行时起着不同的作用,有不同的分配方式和存储内容。对于 C 语言程序员来说,了解这些内存段的特性和用途有助于更好地理解内存管理、变量的存储位置以及程序执行过程中的内存分配情况 1. 代码段 (Code Segment) 内容&a…...
智能合约检测:新一代区块链技术的安全守护
目录 1、智能合约检测:新一代区块链技术的安全守护 2、智能合约性能检测步骤...
PPT|230页| 制造集团企业供应链端到端的数字化解决方案:从需求到结算的全链路业务闭环构建
制造业采购供应链管理是企业运营的核心环节,供应链协同管理在供应链上下游企业之间建立紧密的合作关系,通过信息共享、资源整合、业务协同等方式,实现供应链的全面管理和优化,提高供应链的效率和透明度,降低供应链的成…...
全球首个30米分辨率湿地数据集(2000—2022)
数据简介 今天我们分享的数据是全球30米分辨率湿地数据集,包含8种湿地亚类,该数据以0.5X0.5的瓦片存储,我们整理了所有属于中国的瓦片名称与其对应省份,方便大家研究使用。 该数据集作为全球首个30米分辨率、覆盖2000–2022年时间…...
渲染学进阶内容——模型
最近在写模组的时候发现渲染器里面离不开模型的定义,在渲染的第二篇文章中简单的讲解了一下关于模型部分的内容,其实不管是方块还是方块实体,都离不开模型的内容 🧱 一、CubeListBuilder 功能解析 CubeListBuilder 是 Minecraft Java 版模型系统的核心构建器,用于动态创…...
【决胜公务员考试】求职OMG——见面课测验1
2025最新版!!!6.8截至答题,大家注意呀! 博主码字不易点个关注吧,祝期末顺利~~ 1.单选题(2分) 下列说法错误的是:( B ) A.选调生属于公务员系统 B.公务员属于事业编 C.选调生有基层锻炼的要求 D…...
JVM 内存结构 详解
内存结构 运行时数据区: Java虚拟机在运行Java程序过程中管理的内存区域。 程序计数器: 线程私有,程序控制流的指示器,分支、循环、跳转、异常处理、线程恢复等基础功能都依赖这个计数器完成。 每个线程都有一个程序计数…...
为什么要创建 Vue 实例
核心原因:Vue 需要一个「控制中心」来驱动整个应用 你可以把 Vue 实例想象成你应用的**「大脑」或「引擎」。它负责协调模板、数据、逻辑和行为,将它们变成一个活的、可交互的应用**。没有这个实例,你的代码只是一堆静态的 HTML、JavaScript 变量和函数,无法「活」起来。 …...
LCTF液晶可调谐滤波器在多光谱相机捕捉无人机目标检测中的作用
中达瑞和自2005年成立以来,一直在光谱成像领域深度钻研和发展,始终致力于研发高性能、高可靠性的光谱成像相机,为科研院校提供更优的产品和服务。在《低空背景下无人机目标的光谱特征研究及目标检测应用》这篇论文中提到中达瑞和 LCTF 作为多…...
TCP/IP 网络编程 | 服务端 客户端的封装
设计模式 文章目录 设计模式一、socket.h 接口(interface)二、socket.cpp 实现(implementation)三、server.cpp 使用封装(main 函数)四、client.cpp 使用封装(main 函数)五、退出方法…...
Mysql故障排插与环境优化
前置知识点 最上层是一些客户端和连接服务,包含本 sock 通信和大多数jiyukehuduan/服务端工具实现的TCP/IP通信。主要完成一些简介处理、授权认证、及相关的安全方案等。在该层上引入了线程池的概念,为通过安全认证接入的客户端提供线程。同样在该层上可…...
LeetCode 0386.字典序排数:细心总结条件
【LetMeFly】386.字典序排数:细心总结条件 力扣题目链接:https://leetcode.cn/problems/lexicographical-numbers/ 给你一个整数 n ,按字典序返回范围 [1, n] 内所有整数。 你必须设计一个时间复杂度为 O(n) 且使用 O(1) 额外空间的算法。…...
