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

P5536 【XR-3】核心城市

时间:2023-04-23 19:58:01浏览次数:41  
标签:选择 ch P5536 中心 int 核心 叶子 read XR

P5536 【XR-3】核心城市

请先阅读这个

考虑 \(k = 1\) 时,我们必须选择树的中心。猜测 \(k \ge 1\) 时也要选择树的中心。

首先可以发现,只要我们选择树的中心,则答案一定不会超过树的半径。

现在令树的中心为根。不难发现只要 \(n \ge 3\),这个根就有两个子树。

由于我们选择的 \(k\) 个点必须联通,所以如果我们不选择树的中心,就只能在树的中心的某个儿子 \(s_1\) 的子树里选。这会导致树的中心的另一个儿子 \(s_2\) 最深的叶子节点到达我们选择的 \(k\) 个点的距离超过树的半径,因此是不优的。

\(n \le 2\) 的情况,这个时候所有点都是中心,肯定要选。

证毕,我们必选树的中心。

因此令树的任意一个中心为根,选择以根的一棵子树即可。

不难发现这个贪心思路:看哪边的叶子距离它最近的被选的祖先最远,就把这个祖先的儿子给选上。

或者甚至不用找根,从叶子出发就好。因为 \(n \ge 3\) 的时候,以树的中心为根时的叶子和无根意义下的叶子其实是等价的。所以直接从无根意义下的叶子开始慢慢往里选 \(n - k\) 个点作为最后不选的点即可。再次手玩 \(n \le 2\) 发现也是合法的。

从叶子出发找多源最长路,普通 bfs 有困难,可以考虑魔改拓扑。每次我们只需要处理度数为 \(1\) 的点(叶子),并把这个叶子删去即可。

这个方法虽然简便但是也要依赖上面那个找根做法的证明。题解中找规律式的说明我不是很认可。

/*
 * @Author: crab-in-the-northeast 
 * @Date: 2023-04-23 19:07:23 
 * @Last Modified by: crab-in-the-northeast
 * @Last Modified time: 2023-04-23 19:33:09
 */
#include <bits/stdc++.h>
inline int read() {
    int x = 0;
    bool f = true;
    char ch = getchar();
    for (; !isdigit(ch); ch = getchar())
        if (ch == '-')
            f = false;
    for (; isdigit(ch); ch = getchar())
        x = (x << 1) + (x << 3) + ch - '0';
    return f ? x : (~(x - 1));
}

const int maxn = (int)1e5 + 5;
std :: vector <int> G[maxn];
int deg[maxn], dis[maxn];

int main() {
    int n = read(), k = n - read();
    std :: queue <int> q;
    for (int i = 1; i < n; ++i) {
        int u = read(), v = read();
        G[u].push_back(v);
        G[v].push_back(u);
        ++deg[u];
        ++deg[v];
    }

    for (int u = 1; u <= n; ++u) {
        if (deg[u] == 1) {
            q.push(u);
            dis[u] = 1;
        }
    }

    int ans = 0;

    while (!q.empty() && k) {
        int u = q.front();
        q.pop();
        ans = dis[u];
        --k;
        for (int v : G[u]) {
            --deg[v];
            if (deg[v] == 1) {
                dis[v] = dis[u] + 1;
                q.push(v);
            }
        }
    }

    printf("%d\n", ans);
    return 0;
}

标签:选择,ch,P5536,中心,int,核心,叶子,read,XR
From: https://www.cnblogs.com/crab-in-the-northeast/p/luogu-p5536.html

相关文章

  • dataCompare核心功能之数据探针
    1数据探针产生的背景在数据开发和接入的过程中,数据开发人员接到一个需求或者一条新的业务线可能需要搭建数仓,做数据处理,然后提供一些指标数据给到需求方,如果是你这边会怎么开始呢?直接开干?抽表,清洗,分层,建模?然后发现做完之后,怎么数据各种不对,取不到想要的数据,比如说:业务上说明明一个......
  • 快速上手Linux核心命令(三):文件和目录操作命令
    @目录前言cd切换目录pwd显示当前路径ls显示目录下内容及相关属性信息mkdir创建目录tree以树形结构显示目录下的内容touch创建空白文件或改变文件的时间戳属性cp复制文件或目录mv移动或重命名文件rm删除文件或目录chown改变文件或目录的用户用户组chmod改变文件或目录的......
  • [Linux]raspbian安装xrdp(远程桌面)
    1.首先换源:输入以下命令sudosed-i"s@http://deb.debian.org@https://mirrors.163.com@g"/etc/apt/sources.list2.update是更新软件列表,upgrade是更新软件。这两个命令一般是一起使用的。3.需要在Debian系统中安装xrdp,xrdpisadaemonthatsupportsMicrosoft'sRemote......
  • Java核心机制
    Java核心机制1.Java虚拟机1.JVM是一个虚拟的计算机,具有指令集并使用不同的存储区域。负责执行指令,管理数据,内存,寄存器。2.对于不同的平台,有不同的虚拟机。3.Java虚拟机机制屏蔽了底层运行平台的差别,实现了“一次编译,到处运行”。2.垃圾自动回收1.垃圾回收:不再使用的内存空间......
  • 快速上手Linux核心命令(一):核心命令简介
    Linux核心命令系列文章目录快速上手Linux核心命令(一):核心命令简介快速上手Linux核心命令(二):关机、重启快速上手Linux核心命令(三):文件和目录操作命令快速上手Linux核心命令(四):文件内容相关命令快速上手Linux核心命令(五):文本处理三剑客快速上手Linux核心命令(六):Linux的文本编辑器vi......
  • 数据库校验用户核心代码实现、用户密码加密存储
    数据库校验用户核心代码实现核心代码实现创建一个UserDetailsService接口,重写其中的方法。更加用户名从数据库中查询信息@ServicepublicclassUserDetailsServiceImplimplementsUserDetailsService{@AutowiredprivateUserMapperuserMapper;@Overrid......
  • 领域驱动设计-软件核心复杂性应对之道:第三章
    三、绑定模型和实现模型种类繁多,目的各有不同,即使是那些仅用于软件开发项目的模型也是如此。领域驱动设计要求模型不仅能够指导早期的分析工作,还应该成为设计的基础。这种设计方法对于代码的编写有着重要的暗示作用。不太明显的一点就是:领域驱动设计要求一种不同的建模方法...........
  • 微服务架构下的核心话题 (三):微服务架构的技术选型
    前期回顾:微服务架构下的核心话题(一):微服务架构下各类项目的顺势崛起微服务架构下的核心话题(二):微服务架构的设计原则和核心话题一、前言为了实现基于微服务开发的产品,或者说为了将单体应用重构为微服务架构时,将面临着众多技术框架的选择。大公司往往会有专门的部门或团队来负......
  • 七大关键技术,华为云数据库GaussD承载金融级核心系统
    金融行业,尤其是银行业是对数据库依赖度极高、又对数据库要求最为严苛的行业。随着互联网及移动互联网技术的兴起,网上银行、手机银行、电子支付等新业态出现,高并发、海量数据、超高峰值等挑战接踵而至,导致数据资源存储、计算和应用等需求大幅提升。以往银行业务架构采用的大/小型机+......
  • 团体程序设计天梯赛 L1-064 估值一亿的AI核心代码 题解
    思路L1-064估值一亿的AI核心代码题意有一点不太清晰的,就是原文中的'I',无论是否是单独的,都不能变为小写。如果是单独的'I'再被转化为'you'。这种模拟题就需要每个的分分清清楚楚的,不要都揉到一块儿,容易写错。具体还有些需要注意的在代码里注释着了。代码#include<iostream>......