首页 > 其他分享 >P5536 【XR-3】核心城市

P5536 【XR-3】核心城市

时间:2024-04-02 19:23:53浏览次数:21  
标签:P5536 int 核心 back 100005 XR tie

原题链接

题解

1.这k个城市一定是连成一团在中间的
2.把树展开,变成散发图,剩下的n-k个城市一定在最边缘的位置
3.拓扑排序

dalao's blog

code

#include<bits/stdc++.h>
using namespace std;
vector<int> G[100005];
int du[100005]={0};
int depth[100005]={0};

int main()
{
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int n,k;
    cin>>n>>k;

    for(int i=1;i<n;i++)
    {
        int x,y;
        cin>>x>>y;
        G[x].push_back(y);
        G[y].push_back(x);
    }

    queue<int> q;
    for(int i=1;i<=n;i++)
    {
        du[i]=G[i].size();
        if(du[i]==1) q.push(i);
    }
    int left=n-k,ans=0;
    while(left--)
    {
        int now=q.front();
        q.pop();
        ans=max(ans,depth[now]);
        for(auto next:G[now])
        {
            if(--du[next]==1)
            {
                depth[next]=depth[now]+1;
                q.push(next);
            }
        }
    }

    cout<<ans+1;
    return 0;
}

标签:P5536,int,核心,back,100005,XR,tie
From: https://www.cnblogs.com/pure4knowledge/p/18111333

相关文章

  • 2024最新分享我的面经总结:Java面试技术点攻略(九大核心专题
    关于操作系统这一部分,其实问的内容并不多,主要是因为这一部分问来问去也都是那么几个同样的问题,例如线程通信,线程与进程区别,进程调度算法以及虚拟内存、物理内存等。所以,在这一方面,我也整理了一些相对核心的内容。核心三:MySQL=========MySQL就更不用多说了,数据库不问......
  • Matlab|【核心复现】同时考虑考虑孤岛与重构的配电网故障恢复运行策略
    目录 主要内容     基本知识   1.问题引出2.可控负荷3.网络拓扑约束4.算法流程  结果一览   1.原文结果2.程序运行结果下载链接 主要内容   该模型复现文章《同时考虑考虑孤岛与重构的配电网故障恢复运行策略》,以IEEE33配电网为分析对象,通过......
  • 解析Apache Kafka:在大数据体系中的基本概念和核心组件
    关联阅读博客文章:探讨在大数据体系中API的通信机制与工作原理关联阅读博客文章:深入解析大数据体系中的ETL工作原理及常见组件关联阅读博客文章:深度剖析:计算机集群在大数据体系中的关键角色和技术要点关联阅读博客文章:深入理解HDFS工作原理:大数据存储和容错性机制解析引......
  • 深入解析Java中的核心数据结构:从基础到进阶实战
    在软件开发领域,熟悉并掌握数据结构对于提升程序性能和优化算法至关重要。本文将全面介绍Java中常用的核心数据结构,辅以示例代码和概念图解,以帮助读者更好地理解和应用这些数据结构。1.数组(Array)数组是Java中最基础的数据结构之一,它是在内存中一块连续区域存放相同类型元......
  • 线程池 核心原理
    文章目录线程池核心原理ThreadPoolExecutor主要构造函数:执行任务:关闭线程池:线程池生命周期:Executor框架线程池实战步骤1:创建线程池步骤2:创建任务步骤3:提交任务到线程池步骤4:关闭线程池完整示例线程池核心原理线程池的核心原理是基于“池化”(Pooling)思想,这种思想在......
  • 史上最全Java核心面试题(带全部答案)2024年最新版
    今天要谈的主题是关于求职,求职是在每个技术人员的生涯中都要经历多次。对于我们大部分人而言,在进入自己心仪的公司之前少不了准备工作,有一份全面细致面试题将帮助我们减少许多麻烦。在跳槽季来临之前,特地做这个系列的文章,一方面帮助自己巩固下基础,另一方面也希望帮助想要换工......
  • SQL SERVER 从入门到精通 第5版 第二篇 核心技术 第5章 读书笔记
     第五章SQL基础 P63.SQL概述>.SQL的组成>.数据定义语言(datadefinitionlanguage,DDL):用于在数据库系统中,对数据库,表,视图,索引等数据库对象进行创建和管理>.数据控制语言(datacontrollanguage,DCL):实现对数据库中数据的完整性,完全性等的......
  • 一文掌握堆(Heap)全貌:原理深度解析、动态演示核心操作与实际应用场景
    参考动画:从堆的定义到优先队列、堆排序建议配合动画食用为什么叫堆呢?“堆”这个词在数据结构的上下文中通常指的是一种特定的树形数据结构,其命名来源于它的特性和应用。在这种结构中,父节点和子节点之间存在特定的排序关系,这类似于物理世界中堆积的物体——较大或较重的物......
  • 32-3 APP渗透核心 - APP数据包抓取
    环境准备安装模拟器:在PC上安装一个Android模拟器,例如Genymotion、Bluestacks或者AndroidStudio提供的模拟器等。模拟器可以模拟手机环境,让你在PC上运行Android应用程序。下载APP:在模拟器中下载需要进行渗透测试的APP。你可以通过GooglePlay商店、APK文件或者其他渠道获......
  • 学警杯SSTI复现以及SSTI一类题目核心思路
    本题知识点:漏洞存在原因以及基本思路:开发者在涉及程序网页时为了方便将HTML语言作为一个字符串写进了一个python语句中而造成,通过对某个参数传参,进行查找调用python内部的命令执行语句,获得控制权。参考文章:SSTI_OF_FLASK-Huamang'sBlog类似以下题目把HTML语言写在pytho......