ARC 117 D - Miracle Tree
给出一颗树, (Nle 2e5)
要求构造一组 (E_i(1le i le N)) 满足
- (E_ige 1)
- (|E_i-E_j|ge dist(i,j))
- 最小化 (max(E_i))
首先考虑条件二,
不妨 (E_{p_1}<E_{p_2}<...<E_{p_{n-1}}<E_{p_n}),则 (|E_{p_{i+1}}-E_{p_i}|ge dist(p_i,p_{i+1}))
可得 (|E_r-E_l|ge dist (p_l,p_{l+1})+dist(p_{l+1},p_{l+2})+...+dist(p_{r-1},p_r)ge dist(p_l,p_r))
考虑到条件三,要使得 (E_{p_n}) 最小,则 (E_{p_n}=dist(p_1,p_2)+...+dist(p_{n-1},p_n))
问题转化为寻找一个排列,使得 (dist(p_1,p_2)+...+dist(p_{n-1},p_n)) 最小。
如果头尾相同,那显然最小的是欧拉序。
如果头尾不同,那么希望头尾之间原来有的路径是直径。
这个图怎么绿油油的,下次不选这个颜色了
如图,橙色的是直径,只走了一次,其他边都被走了两次。
注意编号。返程访问点的时候也要加,否则不符合条件二。
代码实现上,最后访问直径。
const int N = 2e5 + 10;
int n, dep[N], is[N], son[N], res[N], tim, p, q;
int e, to[N << 1], nxt[N << 1], hd[N];
void add(int u, int v){ to[++e] = v; nxt[e] = hd[u]; hd[u] = e; }
void dfs(int u, int fa){
if(dep[u] > dep[p]) p = u;
for(int i = hd[u]; i; i = nxt[i]){
int v = to[i]; if(v == fa) continue;
dep[v] = dep[u] + 1; dfs(v, u);
}
return;
}
void dfs2(int u, int fa){
is[u] = (u == q);
for(int i = hd[u]; i; i = nxt[i]){
int v = to[i]; if(v == fa) continue;
dfs2(v, u); if(is[v]) is[u] = 1, son[u] = v;
}
return;
}
void dfs3(int u, int fa){
res[u] = ++tim;
for(int i = hd[u]; i; i = nxt[i]){
int v = to[i]; if(v == fa || v == son[u]) continue;
dfs3(v, u);
}
if(son[u]) dfs3(son[u], u);
++tim;
return;
}
int main() {
scanf("%d", &n);
for(int i = 1, u, v; i < n; i++)
scanf("%d%d", &u, &v), add(u, v), add(v, u);
p = 1; dep[1] = 0; dfs(1, 0);
q = p; dep[q] = 0; dfs(q, 0);
dfs2(p, 0); dfs3(p, 0);
for(int i = 1; i <= n; i++)
printf("%d ", res[i]);
return 0;
}