526互联

AtCoder Regular Contest 117 D Miracle Tree

发布时间 2023-04-30 22:54:01作者: zltzlt

洛谷传送门

AtCoder 传送门

第一步就没想到

可以考虑化简限制。设所有点按 \(E_i\) 从小到大排序后顺序是 \(p_1,p_2,...,p_n\)。发现只需满足 \(E_{p_{i+1}} - E_{p_i} \ge \operatorname{dis}(p_i, p_{i+1})\)。证明是对于任意 \(i < j < k\)，若 \(p_i,p_j\) 和 \(p_j,p_k\) 均满足限制，那么 \(E_{p_k} - E_{p_i} = E_{p_k} - E_{p_j} + E_{p_j} - E_{p_i} \ge \operatorname{dis}(p_k, p_j) + \operatorname{dis}(p_j, p_i) \ge \operatorname{dis}(p_k, p_i)\)。

到这里显然每个不等式都可以取等，即 \(E_{p_{i+1}} = E_{p_i} + \operatorname{dis}(p_i, p_{i+1})\)，\(E_{p_n} = 1 + \sum\limits_{i=1}^{n-1} \operatorname{dis}(p_i, p_{i+1})\)。则我们需要找到一个排列 \(p\)，使得 \(\sum\limits_{i=1}^{n-1} \operatorname{dis}(p_i, p_{i+1})\) 最小。

注意到 \(\sum\limits_{i=1}^{n-1} \operatorname{dis}(p_i, p_{i+1}) + \operatorname{dis}(p_n, p_1)\) 最小值为 \(2(n-1)\)，这是因为每条边至少经过两次。取到下界也很简单，\(p\) 取 dfs 序即可。

现在就变成了要最大化 \(\operatorname{dis}(p_1, p_n)\)。\(p_1,p_n\) 取直径端点即可。

code 
// Problem: D - Miracle Tree
// Contest: AtCoder - AtCoder Regular Contest 117
// URL: https://atcoder.jp/contests/arc117/tasks/arc117_d
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;

const int maxn = 200100;

int n, head[maxn], len, s, t;
int point, maxd, p[maxn], f[maxn], tot, a[maxn];
int fa[maxn], dep[maxn], son[maxn], sz[maxn];
int top[maxn];
bool vis[maxn];

struct edge {
	int to, next;
} edges[maxn << 1];

inline void add_edge(int u, int v) {
	edges[++len].to = v;
	edges[len].next = head[u];
	head[u] = len;
}

void dfs(int u, int fa, int d) {
	if (d > maxd) {
		maxd = d;
		point = u;
	}
	for (int i = head[u]; i; i = edges[i].next) {
		int v = edges[i].to;
		if (v == fa) {
			continue;
		}
		dfs(v, u, d + 1);
	}
}

void dfs2(int u, int fa) {
	if (u == t) {
		f[u] = 1;
	}
	for (int i = head[u]; i; i = edges[i].next) {
		int v = edges[i].to;
		if (v == fa) {
			continue;
		}
		dfs2(v, u);
		f[u] |= f[v];
	}
}

void dfs3(int u, int fa) {
	p[++tot] = u;
	int x = -1;
	for (int i = head[u]; i; i = edges[i].next) {
		int v = edges[i].to;
		if (v == fa) {
			continue;
		}
		if (f[v]) {
			x = v;
			continue;
		}
		dfs3(v, u);
	}
	if (x != -1) {
		dfs3(x, u);
	}
}

int dfs4(int u, int f, int d) {
	fa[u] = f;
	sz[u] = 1;
	dep[u] = d;
	int maxson = -1;
	for (int i = head[u]; i; i = edges[i].next) {
		int v = edges[i].to;
		if (v == f) {
			continue;
		}
		sz[u] += dfs4(v, u, d + 1);
		if (sz[v] > maxson) {
			son[u] = v;
			maxson = sz[v];
		}
	}
	return sz[u];
}

void dfs5(int u, int tp) {
	top[u] = tp;
	vis[u] = 1;
	if (!son[u]) {
		return;
	}
	dfs5(son[u], tp);
	for (int i = head[u]; i; i = edges[i].next) {
		int v = edges[i].to;
		if (!vis[v]) {
			dfs5(v, v);
		}
	}
}

inline int qlca(int x, int y) {
	while (top[x] != top[y]) {
		if (dep[top[x]] < dep[top[y]]) {
			swap(x, y);
		}
		x = fa[top[x]];
	}
	if (dep[x] > dep[y]) {
		swap(x, y);
	}
	return x;
}

inline int qdis(int x, int y) {
	return dep[x] + dep[y] - dep[qlca(x, y)] * 2;
}

void solve() {
	scanf("%d", &n);
	for (int i = 1, u, v; i < n; ++i) {
		scanf("%d%d", &u, &v);
		add_edge(u, v);
		add_edge(v, u);
	}
	dfs(1, -1, 1);
	maxd = 0;
	s = point;
	dfs(s, -1, 1);
	t = point;
	dfs2(s, -1);
	dfs3(s, -1);
	dfs4(s, -1, 1);
	dfs5(s, s);
	a[p[1]] = 1;
	for (int i = 2; i <= n; ++i) {
		a[p[i]] = a[p[i - 1]] + qdis(p[i - 1], p[i]);
	}
	for (int i = 1; i <= n; ++i) {
		printf("%d ", a[i]);
	}
}

int main() {
	int T = 1;
	// scanf("%d", &T);
	while (T--) {
		solve();
	}
	return 0;
}