CF1632E2 题解

First Post:

Last Update:

想了一会儿发现高一的时候做过 E1，然后受之前思路启发一下就会了。感觉高一在这方面实力强于现在（

设 表示两点间距离。

首先解决一个问题：对于给定的 和 ，实现函数 ，返回 是否 ，即判断能否通过加边使得 。

此时对于 的点，我们不用管， 对于 的点，我们需要找到一个点 ，使得 ，如果能找到，那么 就不小于 。

假如我们可以维护出所有 的点集 ，那么 也容易得出，我们只需关注 的点集直径，也就是 中距离最大的一对点 ，那么取到 的点一定是 或 。这是经典结论，不再证明。

我们希望找到一个使 最小的 ，也就是使 的最小 。容易证明 在 到 的路径中点取到，这个 的最小值就是 。

上文表明，如果能够维护 的点集 的直径，那么判定问题是简单的。

这也要用到结论：如果两不交点集 的直径分别为 ，，那 的直径端点一定在 四个点中。

所以，在往 中加入点 时，我们比较原来的 ，原来的 和 三者两两之间的距离，选距离最大的一对作为新的直径即可。

解决判定之后来看如何求答案。我们倒序枚举 和 ，不断减小 直到此时 为假，那么 就是 。在减小 时不断往 中加点，维护点集直径即可。

时间复杂度 ，瓶颈在于预处理 LCA 以快速求出两点距离。

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
#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 5;
int n;
vector<int> G[N];
int dep[N];
namespace LCA {
	const int Lg = 19;
	int ST[Lg][N],lg[N];
	int dfn[N];
	int Min(int x,int y) { return dfn[x] < dfn[y] ? x : y;}
	void dfs(int x,int fa) {
		ST[0][dfn[x] = ++dfn[0]] = fa;
		for(auto y : G[x]) 
			if(y != fa) dep[y] = dep[x] + 1,dfs(y,x);
	}
	void init() {
		lg[0] = -1;dfn[0] = 0;dfs(1,0);
		for(int i = 1;i <= n;i++) lg[i] = lg[i >> 1] + 1;
		for(int j = 1;j < Lg;j++)
			for(int i = 1;i + (1 << j) - 1 <= n;i++)
				ST[j][i] = Min(ST[j - 1][i],ST[j - 1][i + (1 << j - 1)]);
	}
	int lca(int x,int y) {
		if(x == y) return x;
		x = dfn[x];y = dfn[y];
		if(x > y) swap(x,y);
		int k = lg[y - (x++)];
		return Min(ST[k][x],ST[k][y-(1<<k)+1]);
	}
	int dis(int x,int y) { return dep[x] + dep[y] - 2 * dep[lca(x,y)];}
}
vector<int> ps[N],S;
int pxu = -1,pxv = -1;
void Add_n(int i) {
	if(pxu == -1) {pxu = pxv = i;S.push_back(i);return;}
	S.push_back(i);
	int nu = pxu,nv = pxv;
	if(LCA::dis(pxu,i) > LCA::dis(nu,nv)) nu = pxu,nv = i;
	if(LCA::dis(pxv,i) > LCA::dis(nu,nv)) nu = i,nv = pxv;
	pxu = nu;pxv = nv;
}
int GetDis() {
	if(pxu == -1) return -1e9;
	return (LCA::dis(pxu,pxv) + 1) >> 1;
}
void Change(int &Ans) {
	for(auto i : ps[Ans]) Add_n(i);
	--Ans;
}
int mxdep;
int ans[N];
inline void Clr(int n) {
	mxdep = LCA::dfn[0] = 0;pxu = pxv = -1;
	for(int i = 0;i <= n;i++)
		G[i].clear(),ps[i].clear(),dep[i] = 0;
}
inline void work(){
	cin >> n;Clr(n);
	for(int i = 1,u,v;i < n;i++)
		cin >> u >> v,G[u].push_back(v),G[v].push_back(u);
	LCA::init();
	for(int i = 1;i <= n;i++) mxdep = max(mxdep,dep[i]),ps[dep[i]].push_back(i);
	int Ans = mxdep;
	for(int x = n;x >= 1;x--) {
		while(Ans >= 0 && GetDis() + x <= Ans) Change(Ans);
		ans[x] = Ans + 1;
	}
	for(int x = 1;x <= n;++x) cout << ans[x] << ' ';
	cout << endl;
}
int main() {
	int T;
	cin >> T;
	while(T--) work();
	return 0;
}
≡