P3629 [APIO2010] 巡逻

发表于 分类于 本文字数： 3.2k 阅读时长 ≈ 4 分钟

思路

对于 的情况，加上一条边时，树上出现了一条环且长为 ，环上的原路径都可以少走一遍，再算上新路径要走一遍。此时答案为 。
我们需要令 尽可能大，即原路径的那条链尽可能长，那么应该取树的直径。

对于 的情况，加上两条边会出现两条环。由于出现的每条环长度比所选链长多一，所以只考虑树上所选链的情况即可。
若想使总步数尽可能小，那么选出的两条链要尽可能多的覆盖树上的路径。且在每条环上，我们都会把环上所有边都经过一遍再走出这条环，两条链重合的部分会重复走，所以两条链的重合部分要尽可能少。
我们巡逻的策略是一但遇到不在环上的点，就优先去走它，然后再想办法走到环上。所以实际答案为 并交。

贪心地取，我们取到的其中一条链一定是树的直径。
粗略证明：
对于我们选的两条链，它们分别越长一定不劣。如果两条链没有重合部分，那么其中一条上半部分选中两条链中间的部分，接到另一条的下半部分，答案不劣。由于两条链都要尽量长，那么第一条链如此操作一定能够取到直径。

第二条链在取的时候我们分类讨论。
设第一条链选出的点共有 个，点集为 ，按照深度顺序排列。

如果第二条链与第一条链没有重叠部分，那么我们对每个 求其子树直径即可。
如果第二条链与第一条链有重叠部分，我们找到重合部分的两个端点 、。那么我们将这条链分为一段重合部分、和两段非重合部分。可以钦定 ，那么 重。

1

我们需要使 并交 最大，那么分别取到 、 的子树内距其最深的深度 、 一定更优。
此时答案为 ，

找到 即可。

令 ，，此时转化为求 （）。
只需要 扫一遍 ，对于每个 维护出最大的 （在求第二条链的时候顺便维护即可）。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
template <typename T>
inline void read(T&x){ //快读
	int w = 0;x = 0;
	char ch = getchar();
	while(ch<'0' || ch>'9'){
		if(ch=='-') w = 1;
		ch = getchar();
	}
	while(ch>='0' && ch<='9'){
		x = (x<<1)+(x<<3)+(ch^48);
		ch = getchar();
	}
	if(w) x = ~x+1;
}
template <typename T,typename...Args>
inline void read(T&t,Args&...args){
	read(t);read(args...);
}
template <typename T>
inline T Max(T x,T y){ return (x > y ? x : y); }
const int N = 1e5+10;
int n,m,cnt;
struct{
	int to,nex;
}edge[N<<1];
int head[N],edge_num;
inline void add(int x,int y){// 存边
	edge[++edge_num].to = y;
	edge[edge_num].nex = head[x];
	head[x] = edge_num;
}
int dis[N],fa[N],vis[N];
inline int bfs(int s,int flag){// 用来找以 s 为根最深的深度对应的点
	memset(dis,0,sizeof(dis));
	queue <int> q;
	q.push(s);
	int idx = 0;
	if(flag) fa[s] = 0; //只有选直径的时候才标记父亲
	while(!q.empty()){
		int now = q.front();
		q.pop();
		for(int i=head[now];i;i=edge[i].nex){
			int tto = edge[i].to;
			if(dis[tto] || tto==s || vis[tto]) continue;
			if(flag) fa[tto] = now;
			dis[tto] = dis[now]+1;
			if(dis[tto]>dis[idx]) idx = tto;
			q.push(tto);
		}
	}
	return idx;
}
int main(){
	// freopen("data.out","r",stdin);
	// freopen("put.out","w",stdout);

	read(n,m);
	for(int i=1,u,v;i<n;++i){
		read(u,v);
		add(u,v); add(v,u);
	}
	int t1 = bfs(1,1),t2 = bfs(t1,1); //求直径
	if(m==1){// k==1
		printf("%d",2*(n-1)-dis[t2]+1);
		return 0;
	}
    // 把直径上的点标记，强制第二次找最深的深度时，只在直径上的点的子树内
	for(int i=t2;i;i=fa[i]) vis[i] = 1;
	int maxdis = dis[t2],maxn = 0;
	for(int i=t2,f,g,maxg=0;i;i=fa[i]){
		vis[i] = 0;// 防止第一个儿子可能统计不到
		t1 = bfs(i,0);// 最大深度

		++cnt;
        // 求 g 和 f
		g = dis[t1]+cnt;
		f = dis[t1]-cnt;
		// 求 max{g + f}
		maxn = Max(maxn,f+maxg);
		maxg = Max(maxg,g);

		t2 = bfs(t1,0);// 求其子树直径
		vis[i] = 1;// 记得加回来
		maxn = Max(maxn,dis[t2]);// 没有重合部分的情况
	}
	printf("%d",2*(n-1)-maxdis-maxn+2);// 答案

	fclose(stdin);
	fclose(stdout);
	return 0;
}