树的直径被定义为树上最远的两点间的距离。
关于求树的直径的两种方式
HXY造公园
题目描述
现在有一个现成的公园，有 n n n 个休息点和 m m m 条双向边连接两个休息点。众所周知，HXY 是一个 SXBK 的强迫症患者，所以她打算施展魔法来改造公园并即时了解改造情况。她可以进行以下两种操作：
- 对某个休息点 x x x，查询公园中可以与该点互相到达的休息点组成的路径中的最长路径。
- 对于两个休息点 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,v2⋯vk，如果对于其中任意的 v i v_i vi 和 v i + 1 ( 1 ≤ i ≤ k − 1 ) v_{i+1}\quad (1\le i\le k-1) vi+1(1≤i≤k−1)，都有边相连接，那么 v j ( 1 ≤ j ≤ k ) v_j\quad(1\le j\le k) vj(1≤j≤k) 所在区域的最长路径就是 k − 1 k-1 k−1。
输入格式
- 第一行，三个正整数，分别为 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 1≤m<n≤20， 1 ≤ q ≤ 5 1\le q\le5 1≤q≤5。
- 对于 60 % 60\% 60% 的数据， 1 ≤ m < n ≤ 2000 1\le m<n \le 2000 1≤m<n≤2000， 1 ≤ q ≤ 1000 1\le q\le 1000 1≤q≤1000。
- 对于 100 % 100\% 100% 的数据， 1 ≤ m < n ≤ 3 × 1 0 5 1 \le m<n \le 3\times 10^5 1≤m<n≤3×105， 1 ≤ q ≤ 3 × 1 0 5 1\le q\le 3\times 10^5 1≤q≤3×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 n−1 条道路连接着这些村庄，每条道路刚好连接两个村庄，从任何一个村庄，都可以通过这些道路到达其他任何一个村庄。每条道路的长度均为 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(1≤K≤2)。接下来 n − 1 n-1 n−1 行，每行两个整数 a , b a,b a,b，表示村庄 a a a 与 b b b 之间有一条道路 ( 1 ≤ a , b ≤ n ) (1 ≤ a, b ≤ n) (1≤a,b≤n)。
输出格式
输出一个整数，表示新建了 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 1≤n≤1000,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 3≤n≤105,1≤K≤2。
解题思路
1.
K
=
1
K=1
K=1时，只需要找到树的直径，此时的总花销为
2
∗
(
n
−
1
)
−
(
L
1
−
1
)
2*(n-1)-(L1-1)
2∗(n−1)−(L1−1),其中
2
∗
(
n
−
1
)
2*(n-1)
2∗(n−1)为原先的总花销，
(
L
1
−
1
)
(L1-1)
(L1−1)为节省的总花销。因为在
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∗(n−1)−(L1−1)−(L2−1)=2∗n−L1−L2。一些细节:因为需要求
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 n−1 条长度为 1 1 1 的道路，每条道路连接两座城市，且任意两座城市都能通过若干条道路相互到达，显然，城市和道路形成了一棵树。
X 国国王决定将 k k k 座城市钦定为 X 国的核心城市，这 k k k 座城市需满足以下两个条件：
- 这 k k k 座城市可以通过道路，在不经过其他城市的情况下两两相互到达。
- 定义某个非核心城市与这 k k k 座核心城市的距离为，这座城市与 k k k 座核心城市的距离的最小值。那么所有非核心城市中，与核心城市的距离最大的城市，其与核心城市的距离最小。你需要求出这个最小值。
输入格式
第一行 2 2 2 个正整数 n , k n,k n,k。
接下来 n − 1 n - 1 n−1 行，每行 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 1≤k<n≤105。
- 1 ≤ u , v ≤ n , u ≠ v 1 \le u,v \le n, u \ne v 1≤u,v≤n,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
Maxdep−dep, 最小的
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;
}
