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

题解:【XR-3】核心城市

时间:2023-12-22 21:56:02浏览次数:43  
标签:p1 int 题解 len rd cx 核心 XR buf

题解:【XR-3】核心城市

思路一:考虑由特例推广到一般

1、很容易想到先考虑一个关键点的情况,然后再推广到一般情况。

2、一个点肯定选距离上最平衡的那个点,即树的中心。接着在中心周围贪心的选剩下的(k-1)个关键点即可。

3、这里有一个误区:

各点到某点的距离最小,是找树的中心而不是重心!!!

各点到某点的距离最小,是找树的中心而不是重心!!!

各点到某点的距离最小,是找树的中心而不是重心!!!

(树的重心:最小化 最大的子树大小;树的中心:最小化 各点到某点的距离,即树的直径的中点)

#include<bits/stdc++.h>
#define F(i,l,r) for(int i=l;i<=r;++i)
#define G(i,r,l) for(int i=r;i>=l;--i)
#define int long long
using namespace std;
char buf[100],*p1=buf,*p2=buf;
inline int gc(){return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,100,stdin),p1==p2)?EOF:*p1++;}
inline int rd(){
	int x=0; char ch; bool f=1;
	while(!isdigit(ch=gc())) f^=(ch=='-');
	do x=(x<<3)+(x<<1)+(ch^48); while(isdigit(ch=gc()));
	return x;
}
const int N=1e5+5;
struct node{ int v,ne; }e[N<<1];
int first[N],dis[N],len[N],pre[N],a[N];
int n,idx=0,k,cx=0,mn=1000000000;
void add(int x,int y){ e[++idx]=(node){y,first[x]}; first[x]=idx;}
void go(int u,int f){
	dis[u]=dis[f]+1; pre[u]=f;
	if(dis[u]>dis[cx]) cx=u;
	for(int i=first[u];i;i=e[i].ne) if(e[i].v!=f) go(e[i].v,u);
}
void dfs(int u,int f){
	len[u]=1; 
	for(int i=first[u];i;i=e[i].ne){
		int v=e[i].v; if(v==f) continue;
		dfs(v,u);
		len[u]=max(len[v]+1,len[u]);
	}
}
signed main(){
	n=rd(),k=rd(); int u,v;
	F(i,1,n-1) u=rd(),v=rd(),add(u,v),add(v,u);
	go(1,0); 
	dis[cx]=0;
	go(cx,0);
	int cnt=1,iii=(dis[cx]+1)/2;
	while(cnt!=iii && pre[cx]) cx=pre[cx],++cnt;
	dfs(cx,0);
	sort(len+1,len+n+1);
	printf("%lld",len[n-k]);
	return 0;
}

思路二:考虑逆向思维

1、发现 “选k个关键点放入圈中” 等同于 “选(n-k)个非关键点出圈”

2、而由题可知,k个关键点是一个连通块,所以叶子结点是最先出圈的。由此确定,删点是从外而内一层层删

3、用topsort模拟删点的过程即可,由于是用广搜实现topsort,因此点是”一轮一轮删的“,删完(n-k)个点后到了第几轮,答案就是几。

代码可参考这位大佬的博客。

标签:p1,int,题解,len,rd,cx,核心,XR,buf
From: https://www.cnblogs.com/superl61/p/17922422.html

相关文章

  • MT6739_MTK6739安卓核心板_mtk核心板定制
    安卓核心板采用MTK方案,基于联发科MT6739平台开发设计,集成GPUPowerVRGE8100570MHz,搭载开放的智能Android操作系统,集成了BASEBAND、UMCP、PMU等核心器件,支持2.4G+5G双频WIFI(可支持1*1MIMO)、BLUETOOTH近距离无线传输技术,支持GNSS无线定位技术,是卓越的全球......
  • 闭合区域面积统计 题解
    题目描述计算一个\(10\times10\)矩阵中由\(1\)围成的图形的面积。如下所示,在\(10\times10\)的二维数组中,\(1\)围住了\(15\)个点,因此面积为\(15\)。000000000000001110000000100100000001001000100010100101......
  • CF1881F Minimum Maximum Distance 题解
    因为白点对\(f_i\)没有贡献,所以可以重构出一棵原树的子树,使得所有的叶子都为标记点且标记点数量不变(没有删去标记点)。因为没有标记被删去且结构不变,所以这棵树的答案与原树答案相同。现在,对于所有节点,到它距离最大的标记点一定在叶子上。那么问题就变为:求出树上任意一点到所有......
  • ISCTF2023部分题解
    WEB:圣杯战争!!!(题解:结局别说遗憾Zn.)解题思路:打开题目链接,代码如下:<?phphighlight_file(__FILE__);error_reporting(0);classartifact{public$excalibuer;public$arrow;publicfunction__toString(){echo"为Saber选择了对的武器!<br>";return$this->excal......
  • 【洛谷 P1093】[NOIP2007 普及组] 奖学金 题解(结构体排序)
    [NOIP2007普及组]奖学金题目描述某小学最近得到了一笔赞助,打算拿出其中一部分为学习成绩优秀的前名学生发奖学金。期末,每个学生都有门课的成绩:语文、数学、英语。先按总分从高到低排序,如果两个同学总分相同,再按语文成绩从高到低排序,如果两个同学总分和语文成绩都相同,那么规......
  • [CF17E] Palisection 题解
    [CF17E]Palisection题解思路直接统计相交的字符串很难数,考虑正难则反。用总共的回文串对数减去相离的回文串个数。设总共有\(tot\)个回文串,用manacher跑出来每个位置的最大回文半径后,使用差分的技巧保存两个数组:\(f_i\)表示以\(i\)为开头的回文串个数,\(g_i\)表示以......
  • CF187A 题解
    原题传送门题目大意如题意翻译。思路分析很水的一道题目,可以将第一个排列\(a\)看作最终排列,接下来每输入一个数,让它与\(a_m\)进行比较,直到两个排列相同。最后看题目范围,\(1≤n≤2\times10^5\),时间复杂度\(\mathcal{O(n)}\),空间复杂度\(\mathcal{O(n)}\)。代码:/*Writ......
  • CF1912L 题解
    原题传送门题目大意有一个仅有0和L构成的序列,求出一种方案,使得左部分的0数量不等于右部分的O数量,且左部分的L数量不等于右部分的L数量,若不存在输出-1。思路分析首先看题目范围,\(2≤n≤200\),数据很小,考虑暴力。可以使用字符串截取函数s.substr()。本题我们使......
  • 为什么程序员会35岁失业?核心原因:一年工作经验用十年!
    前言分享一下身边朋友的亲身经历,也浅浅的安慰一下那些被优化之后,找不到工作的朋友的受伤的心灵,因为你不是一个人!!!(下面由第一人称描述这个故事)距离过年还有三个月了,在这个节骨眼上我失业了。在广州失业已经一个月了,压力大的睡不着,每天梦里都在不停的浏览招聘网站。今天到了一家公司去......
  • P5289 [十二省联考 2019] 皮配 题解
    题目链接点击打开链接题目解法题意比较复杂,形式化一下题意是:一些人和一些城市,每个人属于一个城市,每个人属于\(A/B/C/D\)队,需要满足:每个城市中的人要么都属于\(AC\)或\(BD\),且\(A+C\leC_0,\;B+D\leC_1,\;A+B\leD_0,\;C+D\leD_1\)暴力\(dp\)是\(f_{i,a,b,c}\)表......