Codeforces Round #769 (Div. 2)：E1. Distance Tree (easy version)

Codeforces Round #769 (Div. 2)：E1. Distance Tree (easy version) 距离树

能力有限，只看懂了easy version…

题意：

给定一颗 n 个结点的树， d ( v ) d(v) d(v)代表这颗树上任意点到 1 点的最短距离定义 f ( x ) f(x) f(x)表示：在这棵树上任意两点间加一条权值为 x 的边后， M a x 1 < = v < = n d ( v ) Max_{1<=v<=n}d(v) Max1<=v<=n​d(v)的值对于所有的 x 取值于1~n ，求出对应 f ( x ) f(x) f(x)分析：在树上如何加一条边，能使得各个点到 1点 的最短距离最大值最小

思路：

加边最优的 *** 作显然是 某点连向 1，这个可以自行纸上模拟；我们加边的 *** 作不能只顾及极限点，比如离 1 最远的点；只修改最远点到 1 的距离，不顾及次远点、次次远点是不妥当的；为了使最大值最小，我们最好把 这个加边点 放在 树的中心，每个点到该点的最短距离都相较平均，题解的意思如此，具体证明不能 ；

基于以上前提，题解给了一种很神必的枚举方法 —— 枚举答案（二分答案没了二分 ）

我们每次都假设一个 ans 答案，表示加边后 1 点到最远点的 距离，若加边点是在树的中心上，因为 树的中心 == 树的直径中点 ，我们能得知 树的直径 == 2 ∗ ( a n s − x ) 2*(ans-x) 2∗(ans−x)

在该答案的限制下我们去求 树的直径 为多少，即可判断此时 ans答案 是该保留还是增大（尽可能取小）

是不是跟二分答案很像？

至于限制是什么，限制就是：

若当前 ans == 2，我们求 树的直径 时就不能枚举到 深度dep（离1点距离）<= 2 的点，也就是直径两端的点不可以是这些点，因为这些点可以直接走到 1 上，不影响 ans，加边点的放置是为了优先考虑直径两端的极限点，减少极限点到 1 的距离很玄学的解释，有更好的说法可以交流一下

最后，cf 给的题解是 O ( n 3 ) O(n^3) O(n3)的…亲测极限情况会被 链状树 数据卡成 4s，但出题人好像没出这种数据 如果是我搞错了请指导我

这里给一种排序预处理、指针遍历的做法，稳定 O ( n 2 ) O(n^2) O(n2)

C o d e : Code: Code:

#include
#include
#include
#define mem(a,b) memset(a,b,sizeof a)
#define cinios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0))
#define sca scanf
#define pri printf
#define ul (u << 1)
#define ur (u << 1 | 1)
#define forr(a,b,c) for(int a=b;a<=c;a++)
#define rfor(a,b,c) for(int a=b;a>=c;a--)
//#define x first
//#define y second
//[博客地址](https://blog.csdn.net/weixin_51797626?t=1) 
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair PII;

const int N = 3010, M = 6010, MM = N;
int INF = 0x3f3f3f3f, mod = 1e9 + 7;
ll LNF = 0x3f3f3f3f3f3f3f3f;
int n, m, k, T, S, D;
int h[N], e[M], ne[M], idx;
int d1[N], depdis[N];
struct node
{
	int w, id;
	bool operator<(const node& no)const { return w > no.w; }
}dd[N];

inline void add(int a, int b) {
	e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

void dfs(int x, int fa, int* d) {
	for (int i = h[x]; ~i; i = ne[i]) {
		int j = e[i];
		if (j == fa)continue;
		d[j] = d[x] + 1;
		dfs(j, x, d);
	}
}

void solve() {
	cin >> n;
	idx = 0;
	forr(i, 1, n)h[i] = -1;//注意按数据初始化，memset不要乱用

	forr(i, 1, n - 1) {
		int a, b;
		cin >> a >> b;
		add(a, b), add(b, a);
	}

	int d_dep = 1;//记录离1最远的点
	d1[1] = 0;
	dfs(1, -1, d1);
	forr(i, 1, n)if (d1[i] > d1[d_dep])d_dep = i;

	depdis[d_dep] = 0;
	dfs(d_dep, -1, depdis);//跑一个其他点到最远点的距离

	forr(i, 1, n)dd[i] = { depdis[i],i };//用数组记录下来
	sort(dd + 1, dd + 1 + n);//从大到小排序
	//最大的肯定是树的直径，如果直径的一个端点被覆盖了就舍去，找次直径

	forr(i, 1, n) {
		if (d1[d_dep] <= i) {//如果加的边没有贡献就直接走人
			cout << d1[d_dep] << ' ';
			continue;
		}
		int j = 1, ans = 0;//否则枚举答案
		while (1)
		{
			int max_dist = -1;
			//在此刻被限制的直径，ans变大后肯定也被限制，所以可以指针只跑一遍不循环
			while (j <= n) { 
				int id = dd[j].id;
				if (d1[id] <= ans)j++;//限制
				else {
					max_dist = dd[j].w;
					break;
				}
			}
			if (max_dist == -1)break;//如果找不到说明已经没法更新ans了，退出

			if (max_dist > 2 * (ans - i))ans++;
			else break;//同理
		}
		cout << ans << ' ';

		//预处理能保证两个while循环独立
	}
	cout << 'n';
}

int main() {
	cinios;

	cin >> T;
	while (T--)solve();

	return 0;
}