第一步就没想到
可以考虑化简限制。设所有点按 \(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;
}