Part 8.3.2 树的直径

树的直径被定义为树上最远的两点间的距离。

关于求树的直径的两种方式

HXY造公园

题目描述

现在有一个现成的公园,有 n n n 个休息点和 m m m 条双向边连接两个休息点。众所周知,HXY 是一个 SXBK 的强迫症患者,所以她打算施展魔法来改造公园并即时了解改造情况。她可以进行以下两种操作:

  1. 对某个休息点 x x x,查询公园中可以与该点互相到达的休息点组成的路径中的最长路径。
  2. 对于两个休息点 x , y x,y x,y,如果 x , y x,y x,y 已经可以互相到达则忽略此次操作。否则,在 x x x 可到达的所有休息点和 y y y 可到达的所有休息点(包括 x , y x,y x,y 自身)分别选择一个休息点,然后在这两个休息点之间连一条边,并且这个选择应该满足对于连接后的公园, x x x y y y 所在的区域(即 x , y x,y x,y 可达到的所有休息点和边组成的集合)中的最长路径的长度最小。

HXY打算进行 q q q 个操作,请你回答她的对于公园情况的询问(操作 1)或者执行她的操作(操作 2)。

注:所有边的长度皆为 1 1 1。保证不存在环。最长路径定义为:对于点 v 1 , v 2 ⋯ v k v_1,v_2\cdots v_k v1,v2vk,如果对于其中任意的 v i v_i vi v i + 1 ( 1 ≤ i ≤ k − 1 ) v_{i+1}\quad (1\le i\le k-1) vi+1(1ik1),都有边相连接,那么 v j ( 1 ≤ j ≤ k ) v_j\quad(1\le j\le k) vj(1jk) 所在区域的最长路径就是 k − 1 k-1 k1

输入格式

  • 第一行,三个正整数,分别为 n , m , q n,m,q n,m,q
  • 接下来的 m m m 行,每一行有两个正整数 x i , y i x_i,y_i xi,yi,表示 x i x_i xi y i y_i yi 有一条双向边相连。
  • 再接下来的 q q q 行,每一行表示一个操作。
    • 若该行第一个数为 1 1 1,则表示操作 1,之后还有一个正整数 x i x_i xi,表示要查询的休息点。
    • 若该行第一个数为 2 2 2,则表示操作 2,之后还有两个正整数 x i , y i x_i,y_i xi,yi,表示需要执行操作的两个休息点。

输出格式

输出行数为操作 1 的个数。

每行输出对于操作 1 询问的回答。

样例 #1

样例输入 #1

6 0 6
2 1 2
2 3 4
2 5 6
2 3 2
2 5 3
1 1

样例输出 #1

4

提示

数据范围及约定

  • 对于 10 % 10\% 10% 的数据,只存在操作 1。
  • 对于 30 % 30\% 30% 的数据, 1 ≤ m < n ≤ 20 1\le m<n\le 20 1m<n20 1 ≤ q ≤ 5 1\le q\le5 1q5
  • 对于 60 % 60\% 60% 的数据, 1 ≤ m < n ≤ 2000 1\le m<n \le 2000 1m<n2000 1 ≤ q ≤ 1000 1\le q\le 1000 1q1000
  • 对于 100 % 100\% 100% 的数据, 1 ≤ m < n ≤ 3 × 1 0 5 1 \le m<n \le 3\times 10^5 1m<n3×105 1 ≤ q ≤ 3 × 1 0 5 1\le q\le 3\times 10^5 1q3×105

解题思路

1.使用并查集维护点之间是否在一个集合的关系。
2.对于每一个集合分别求直径,并将直径记录在每个集合的根节点。
3.1则直接返回当前点所在集合的直径。
4.2则合并两个集合,更新长度为 m a x ( m a x ( l e n 1 , l e n 2 ) , ( ( l e n 1 + 1 ) / 2 + ( l e n 2 + 1 ) / 2 ) ) 。 max(max(len1,len2),((len1+1)/2+(len2+1)/2))。 max(max(len1,len2),((len1+1)/2+(len2+1)/2))

code

#include<iostream>
#include<vector>
using namespace std;
#define MAX_N 300000
int n,m,q;
vector<int>e[MAX_N+5];
int fa[MAX_N+5];
int vis[MAX_N+5];
int max_l[MAX_N+5];
int len;
int find(int x)
{
	return fa[x]=(fa[x]==x?x:find(fa[x]));
}
int dfs(int now)
{
	vis[now]=1;
	int d1=0,d2=0;
	for(auto v:e[now])
	{
		if(vis[v])continue;
		int d=dfs(v)+1;
		if(d>d1){d2=d1,d1=d;}
		else if(d>d2){d2=d;}
	}
	len=max(len,d1+d2);
	return d1;
}
int main()
{
	cin>>n>>m>>q;
	for(int i=1;i<=n;i++)fa[i]=i;
	for(int i=1,a,b;i<=m;i++)
	{
		scanf("%d%d",&a,&b);
		fa[find(a)]=find(b);
		e[a].push_back(b);
		e[b].push_back(a);
	}
	for(int i=1;i<=n;i++)
	{
		if(fa[i]!=i)continue;
		len=0;
		dfs(i);
		max_l[i]=len;
	}
	int opt,x,y;
	while(q--)
	{
		scanf("%d",&opt);
		if(opt==1)
		{
			scanf("%d",&x);
			printf("%d\n",max_l[find(x)]);
		}
		else{
			scanf("%d%d",&x,&y);
			int f1=find(x),f2=find(y);
			if(f1==f2)continue;
			max_l[f1]=max(max(max_l[f1],max_l[f2]),(((max_l[f1]+1)>>1)+((max_l[f2]+1)>>1)+1));
			fa[f2]=f1;
		}
	}
	return 0;
}

[APIO2010] 巡逻

题目描述

在一个地区中有 n n n 个村庄,编号为 1 , 2 , … , n 1, 2, \dots, n 1,2,,n。有 n − 1 n-1 n1 条道路连接着这些村庄,每条道路刚好连接两个村庄,从任何一个村庄,都可以通过这些道路到达其他任何一个村庄。每条道路的长度均为 1 1 1 个单位。为保证该地区的安全,巡警车每天要到所有的道路上巡逻。警察局设在编号为 1 1 1 的村庄里,每天巡警车总是从警察局出发,最终又回到警察局。下图表示一个有 8 8 8 个村庄的地区,其中村庄用圆表示(其中村庄 1 1 1 用黑色的圆表示),道路是连接这些圆的线段。为了遍历所有的道路,巡警车需要走的距离为 14 14 14 个单位,每条道路都需要经过两次。

为了减少总的巡逻距离,该地区准备在这些村庄之间建立 K K K 条新的道路,每条新道路可以连接任意两个村庄。两条新道路可以在同一个村庄会合或结束,如下面的图例 ©。一条新道路甚至可以是一个环,即其两端连接到同一个村庄。由于资金有限, K K K 只能是 1 1 1 2 2 2。同时,为了不浪费资金,每天巡警车必须经过新建的道路正好一次。下图给出了一些建立新道路的例子:

在 (a) 中,新建了一条道路,总的距离是 11 11 11。在 (b) 中,新建了两条道路,总的巡逻距离是 10 10 10。在 © 中,新建了两条道路,但由于巡警车要经过每条新道路正好一次,总的距离变为了 15 15 15。试编写一个程序,读取村庄间道路的信息和需要新建的道路数,计算出最佳的新建道路的方案使得总的巡逻距离最小,并输出这个最小的巡逻距离。

输入格式

第一行包含两个整数 n , K ( 1 ≤ K ≤ 2 ) n, K(1 ≤ K ≤ 2) n,K(1K2)。接下来 n − 1 n-1 n1 行,每行两个整数 a , b a,b a,b,表示村庄 a a a b b b 之间有一条道路 ( 1 ≤ a , b ≤ n ) (1 ≤ a, b ≤ n) (1a,bn)

输出格式

输出一个整数,表示新建了 K K K 条道路后能达到的最小巡逻距离。

样例 #1

样例输入 #1

8 1 
1 2 
3 1 
3 4 
5 3 
7 5 
8 5 
5 6

样例输出 #1

11

样例 #2

样例输入 #2

8 2 
1 2 
3 1 
3 4 
5 3 
7 5 
8 5 
5 6

样例输出 #2

10

样例 #3

样例输入 #3

5 2 
1 2 
2 3 
3 4 
4 5

样例输出 #3

6

提示

  • 10 % 10\% 10% 的数据中, 1 ≤ n ≤ 1000 , K = 1 1≤n≤1000,K=1 1n1000,K=1
  • 30 % 30\% 30% 的数据中, K = 1 K=1 K=1
  • 80 % 80\% 80% 的数据中,每个村庄相邻的村庄数不超过 25 25 25
  • 90 % 90\% 90% 的数据中,每个村庄相邻的村庄数不超过 150 150 150
  • 100 % 100\% 100% 的数据中, 3 ≤ n ≤ 1 0 5 , 1 ≤ K ≤ 2 3≤n≤10^5,1≤K≤2 3n105,1K2

解题思路

1. K = 1 K=1 K=1时,只需要找到树的直径,此时的总花销为 2 ∗ ( n − 1 ) − ( L 1 − 1 ) 2*(n-1)-(L1-1) 2(n1)(L11),其中 2 ∗ ( n − 1 ) 2*(n-1) 2(n1)为原先的总花销, ( L 1 − 1 ) (L1-1) (L11)为节省的总花销。因为在 L 1 L1 L1两端连上之后,可以省去一整个距离为 L 1 L1 L1的往返,而被一个长度 1 1 1所代替。
2. K = 2 K=2 K=2时,分两步来进行,首先依然是先找到 L 1 L1 L1,之后将 L 1 L1 L1路径上所有点的权值设为 − 1 -1 1,之后再进行一次求解得到 L 2 L2 L2,答案为 2 ∗ ( n − 1 ) − ( L 1 − 1 ) − ( L 2 − 1 ) = 2 ∗ n − L 1 − L 2 2*(n-1)-(L1-1)-(L2-1)=2*n-L1-L2 2(n1)(L11)(L21)=2nL1L2。一些细节:因为需要求 L 1 L1 L1所经过的路径,所以第一遍需要两次dfs来求解;因为第二次 L 1 L1 L1上的路径权值被置为 − 1 -1 1,所以第二遍要用 d p dp dp的方式求解。

code

#include<iostream>
#include<vector>
using namespace std;
#define MAX_N 100000
int n,k;
struct edge{
	int v,w;
};
vector<edge>e[MAX_N+5];
int road[MAX_N+5];
int id;
int l1,l2;
int flag=0;
void dfs(int now,int fa,int weight)
{
	if(l1<weight)
	{
		id=now;
		l1=weight;
	}
	for(auto nxt:e[now])
	{
		int v=nxt.v,w=nxt.w;
		if(v==fa)continue;
		dfs(v,now,weight+w);
	}
	return ;
}
void mark(int now,int fa,int ed)
{
	for(auto nxt:e[now])
	{
		int v=nxt.v;
		if(flag==1)return ;
		if(v==fa)continue;
		if(v==ed)
		{
			flag=1;
			road[now]=ed;
			return ;
		}
		road[now]=v;
		mark(v,now,ed);
	}
	return ;
}
void change(int now,int ed)
{
	for(int i=0;i<e[now].size();i++)
	{
		if(e[now][i].v!=road[now])continue;
		e[now][i].w=-1;
		if(e[now][i].v==ed)return ;
		change(road[now],ed);
	}
	return ;
}
int dfs2(int now,int fa)
{
	int d1=0,d2=0;
	for(auto nxt:e[now])
	{
		int v=nxt.v,w=nxt.w;
		if(fa==v)continue;
		int d=dfs2(v,now)+w;
		if(d>d1){d2=d1,d1=d;}
		else if(d>d2){d2=d;}
		l2=max(l2,d1+d2);
	}
	return d1;
}
int main()
{
	cin>>n>>k;
	for(int i=1,a,b;i<=n-1;i++)
	{
		scanf("%d %d",&a,&b);
		e[a].push_back({b,1});
		e[b].push_back({a,1});
	}
	dfs(1,0,0);
	int st=id;l1=0;
	dfs(st,0,0);
	int ed=id;
	if(k==1)
	{
		cout<<2*(n-1)-l1+1;
		return 0;
	}
	mark(st,0,ed);
	change(st,ed);
	dfs2(st,0);
	cout<<2*(n-1)-l1-l2+2;
	return 0;
 } 

【XR-3】核心城市

题目描述

X 国有 n n n 座城市, n − 1 n - 1 n1 条长度为 1 1 1 的道路,每条道路连接两座城市,且任意两座城市都能通过若干条道路相互到达,显然,城市和道路形成了一棵树。

X 国国王决定将 k k k 座城市钦定为 X 国的核心城市,这 k k k 座城市需满足以下两个条件:

  1. k k k 座城市可以通过道路,在不经过其他城市的情况下两两相互到达。
  2. 定义某个非核心城市与这 k k k 座核心城市的距离为,这座城市与 k k k 座核心城市的距离的最小值。那么所有非核心城市中,与核心城市的距离最大的城市,其与核心城市的距离最小。你需要求出这个最小值。

输入格式

第一行 2 2 2 个正整数 n , k n,k n,k

接下来 n − 1 n - 1 n1 行,每行 2 2 2 个正整数 u , v u,v u,v,表示第 u u u 座城市与第 v v v 座城市之间有一条长度为 1 1 1 的道路。

数据范围:

  • 1 ≤ k < n ≤ 1 0 5 1 \le k < n \le 10 ^ 5 1k<n105
  • 1 ≤ u , v ≤ n , u ≠ v 1 \le u,v \le n, u \ne v 1u,vn,u=v,保证城市与道路形成一棵树。

输出格式

一行一个整数,表示答案。

样例 #1

样例输入 #1

6 3
1 2
2 3
2 4
1 5
5 6

样例输出 #1

1

提示

【样例说明】

钦定 1 , 2 , 5 1,2,5 1,2,5 3 3 3 座城市为核心城市,这样 3 , 4 , 6 3,4,6 3,4,6 另外 3 3 3 座非核心城市与核心城市的距离均为 1 1 1,因此答案为 1 1 1

解题思路

以树的直径中点为根,设每个节点的深度为 d e p dep dep ,其后代节点最大深度为 M a x d e p Maxdep Maxdep ,则
k k k个核心节点为 M a x d e p − d e p Maxdep−dep Maxdepdep, 最小的 k k k个点。
先求出树的直径,过程中记录每个节点的父亲以及树的直径的叶子节点。然后递归遍历找中点。最后贪心求答案即可。

code

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
#define MAX_N 100000
int n,k;
vector<int>e[MAX_N+5];
int chdeep[MAX_N+5],deep[MAX_N+5];
int road[MAX_N+5];
int _max=0,id;
int st,ed;
int flag;
int maxx=0;
bool cmp(int a,int b)
{
	return a>b;
}
void dfs1(int now,int fa,int s)
{
	if(_max<s)
	{
		id=now;
		_max=s;
	}
	for(auto v:e[now])
	{
		if(v==fa)continue;
		dfs1(v,now,s+1);
	}
	return ;
}
void dfs2(int now,int fa,int ed)
{
	for(auto v:e[now])
	{
		if(v==fa)continue;
		if(flag)return ;
		if(v==ed)
		{
			road[now]=v;
			flag=1;
			return ;
		}
		road[now]=v;
		dfs2(v,now,ed);
	}
	return ;
}
void dfs3(int now,int fa)
{
	chdeep[now]=deep[now];
	for(auto v:e[now])
	{
		if(v==fa)continue;
		deep[v]=deep[now]+1;
		dfs3(v,now);
		chdeep[now]=max(chdeep[now],chdeep[v]);
	}
	return ;
}
int main()
{
	cin>>n>>k;
	for(int i=1,a,b;i<=n-1;i++)
	{
		scanf("%d %d",&a,&b);
		e[a].push_back(b);
		e[b].push_back(a);
	}
	dfs1(1,0,0);
	st=id;
	_max=0;
	dfs1(st,0,0);
	ed=id;
	dfs2(st,0,ed);
	int mid=st;
	for(int i=1;i<=_max/2;i++)mid=road[mid];
	dfs3(mid,0);
	for(int i=1;i<=n;i++)chdeep[i]-=deep[i];
	sort(chdeep+1,chdeep+n+1,cmp);
	for(int i=k+1;i<=n;i++)maxx=max(maxx,chdeep[i]+1);
	cout<<maxx;
	return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.mfbz.cn/a/748887.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

彩虹PLM系统:引领汽车行业的数字化转型

彩虹PLM系统&#xff1a;引领汽车行业的数字化转型 彩虹PLM系统作为汽车行业数字化转型的引领者&#xff0c;凭借其卓越的技术实力和丰富的行业经验&#xff0c;为汽车行业带来了全面的解决方案。以下是彩虹PLM系统如何引领汽车行业数字化转型的详细分析&#xff1a; 一、整合全…

虚拟机使用的是此版本 VMware Workstation 不支持的硬件版本

复制了同事的VMware镜像&#xff0c;但是他的软件版本和我的不同&#xff0c;于是乎出现了这个报错&#xff1a;虚拟机使用的是此版本 VMwareWorkstation 不支持的硬件版本。 模块“Upgrade”启动失败。 解决办法&#xff0c;直接改.vmx文件的版本信息&#xff1a; 以文本格式打…

ROS学习(17):定位和地图绘制(1)

目录 0.前言 1.定位和建图 1.里程计&#xff08;Odometry&#xff09; 2.扫描匹配&#xff08;Scan Matching&#xff09; 3.结尾 0.前言 好久不见各位&#xff0c;前段时间忙着考试&#xff08;6级和一些专业课&#xff09;和摆烂断更了近30天&#xff0c;现在哥们回来更…

约课健身管理系统小程序源码

健身达人的智能助手 一款基于FastAdminThinkPHPUniapp开发的米扬约课健身管理系统&#xff0c;应用于健身房&#xff0c;健身工作室&#xff0c;运动会所&#xff0c;运动场馆&#xff0c;瑜伽馆&#xff0c;拳馆等泛健身行业的场馆中。米扬约课健身致力于为各种健身场馆打造真…

四川赤橙宏海商务信息咨询有限公司好不好?

在当今数字化浪潮下&#xff0c;电商行业正以前所未有的速度发展&#xff0c;而抖音作为短视频领域的佼佼者&#xff0c;其电商服务更是成为了众多品牌争相布局的热门领域。四川赤橙宏海商务信息咨询有限公司&#xff0c;正是这样一家专注于抖音电商服务的领军企业&#xff0c;…

快速阅读参考文献:kimi请求出战!

学境思源&#xff0c;一键生成论文初稿&#xff1a; AcademicIdeas - 学境思源AI论文写作 上篇文章&#xff0c;我们为大家演示了“如何使用kimi创建论文中的流程图”。今天继续为大家介绍“使用kimi快速阅读学术参考文献”。 在学术研究的海洋中&#xff0c;文献阅读是一项基…

解决chrome浏览器Console控制台无法粘贴代码

【问题】 浏览器调试的时候经常会用到console&#xff0c;粘贴内容进console控制台会报错&#xff0c;严重影响调试效率。 报错内容如下&#xff1a; Warning: Don’t paste code into the DevTools Console that you don’t understand or haven’t reviewed yourself. Thi…

ZAP安全扫描工具

下载地址: 去官网下载&#xff1a;https://www.zaproxy.org/download/ 1.主动扫描 需要登录的网站建议使用主动扫描 也可以绕过登录进行手动扫描 再选择手动扫描后 获取到对应的token 2.自动扫描 3.查看报告 4.扫描策略的使用

Java版本Spring Cloud+SpringBoot b2b2c:Java商城实现一件代发设置及多商家直播带货商城搭建

一、产品简介 我们的JAVA版多商家入驻直播带货商城系统是一款全*面的电子商务平台&#xff0c;它允许商家和消费者在一个集成的环境中进行互动。系统采用先进的JAVA语言开发&#xff0c;提供多商家入驻、直播带货、B2B2C等多种功能&#xff0c;帮助用户实现线上线下的无缝对接…

【python】pop()函数

python pop() &#xff0c;如何在Python的列表或数组中移除元素 使用 pop() 从列表中删除元素 pop() 语法概述 pop() 方法的语法如下&#xff1a; list_name.pop(index)list_name&#xff1a;列表变量名&#xff1b;内置的 pop() 方法仅需要一个可选参数&#xff1b;可选参…

浅谈逻辑控制器之交替控制器

浅谈逻辑控制器之交替控制器 本文档将详细介绍其中一种重要逻辑控制器——交替控制器 (Interleave Controller)&#xff0c;并提供其使用方法和应用场景。 交替控制器概述 交替控制器 (Interleave Controller) 是 JMeter 中的一个高级逻辑控制器&#xff0c;它使你能够按照交…

【vue3】【vant】 移动本草纲目案例发布收藏项目源码

更多项目点击&#x1f446;&#x1f446;&#x1f446;完整项目成品专栏 【vue3】【vant】 移动本草纲目案例发布收藏项目源码 获取源码方式项目说明&#xff1a;其中功能包括 项目包含&#xff1a;项目运行环境文件截图 获取源码方式 加Q群&#xff1a;632562109项目说明&am…

应用案例 | Panorama SCADA:开创性的铁路电气控制系统

案例概况 客户&#xff1a;英国铁路网运营商Network Rail 合作伙伴&#xff1a;Telent Technology Services Ltd 应用&#xff1a;实现对铁路牵引电网的高效管理与精准控制 应用产品&#xff1a;宏集Panorama E2 SCADA系统 一、应用背景 英国铁路网运营商Network Rail计划…

谈论Fail2ban+Nginx处理CC攻击和DDOS攻击

前言&#xff1a;Fail2ban 是一款开源的入侵防御软件&#xff0c;用于防止暴力破解和其他形式的恶意攻击。虽然它主要设计用于检测和阻止基于日志的暴力破解尝试&#xff0c;但也可以用于处理低强度的CC&#xff08;Challenge Collapsar&#xff09;和部分DDoS&#xff08;分布…

Python高精度浮点运算库之mpmath使用详解

概要 在科学计算和工程应用中,精确的数学计算至关重要。Python 作为一种灵活而强大的编程语言,提供了多种数学库,其中 mpmath 库因其高精度浮点运算和丰富的数学函数支持而备受关注。mpmath 库不仅适用于基本的高精度计算,还支持复数运算、矩阵运算和特殊函数计算,广泛应…

Python第三方库GDAL 安装

安装GDAL的方式多种&#xff0c;包括pip、Anaconda、OSGeo4W等。笔者在安装过程中&#xff0c;唯独使用pip安装遇到问题。最终通过轮子文件&#xff08;.whl&#xff09;成功安装。 本文主要介绍如何下载和安装较新版本的GDAL轮子文件。 一、GDAL轮子文件下载 打开Github网站…

Swoole v6 能否让 PHP 再次伟大?

大家好&#xff0c;我是码农先森。 现状 传统的 PHP-FPM 也是多进程模型的的运行方式&#xff0c;但每个进程只能处理完当前请求&#xff0c;才能接收下一个请求。而且对于 PHP 脚本来说&#xff0c;只是接收请求和响应请求&#xff0c;并不参与网络通信。对数据库资源的操作…

创纪录!沃飞长空完成新一轮融资,实力获资方认可

作为全球竞逐的战略性新兴产业&#xff0c;今年首次写入政府工作报告的“低空经济”热度正持续提升&#xff0c;在政策、产业等多个层面均有重大突破。行业的飞速发展也吸引了投资界的目光&#xff0c;越来越多资本正投向低空经济。 近期&#xff0c;国内领先的低空出行企业吉…

zabbix 7.0 新增功能亮点(三)— 监控项支持SNMP Hex数据预处理

作者 乐维社区&#xff08;forum.lwops.cn&#xff09; 许远 勇敢的人先享受世界&#xff0c;好奇心促使你探索未知的世界。zabbix 7.0 LTS发布已经有一段时间了。不得不说zabbix7.0作为一款开源监控工具而言是真的强大又丝滑&#xff0c;其中不少新特性嘎嘎溜&#xff0c;让人…

互联网医院系统开发中的移动端应用设计

在现代医疗服务中&#xff0c;互联网医院系统逐渐成为提升患者体验和优化医疗资源的重要手段。而移动端应用作为互联网医院系统的关键组成部分&#xff0c;其设计和开发尤为重要。本文将从设计原则、技术架构和具体实现等方面探讨互联网医院系统中的移动端应用设计&#xff0c;…