[ARC117D] Miracle Tree

Creator_157 · 2022-11-20 07:00:43 · 题解

题意

给定一棵 n 个节点的树，要求构造出一个点权序列 E，满足以下三个条件：

1.所有 E_i\ge 1(1\le i\le n)。

2.对于任意一组 (i,j)(1 ≤ i < j ≤ N)，使 |E_i-E_j|\ge dist(i,j)，dist 即树上两点距离。

3.使 E 中的最大值最小。

题解

考虑一种构造方式：从一个点开始进行 \text{DFS}，同时维护一个当前要填的数 cnt，每次经过一条边就 ++cnt（回溯时也一样，因为要使回溯到的点与他的儿子也满足第二条限制）。

这样保证了对于每一个点，它能到达的点至少与它满足第二条限制。

但是这可能导致不满足第三条限制。

发现：最终最大的标号是经过的边的次数 +1，并且不一定要回到根。

所以我们可以利用一个经典套路优化以上策略，选定直径作为只经过一次的边（不用回溯），以直径的一端为根进行编号，到另一端就结束。这样使得最大的编号（总边数 \times 2- 没有回溯的边数）最小。

code

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define re int
#define Bessie signed
int read()
{
    int A = 0, FL = 1;
    char CH = getchar();
    while(CH < '0' || CH > '9')
        FL = (CH == '-') ? -1 : 1, CH = getchar();
    while(CH >= '0' && CH <= '9')
        A = (A << 3) + (A << 1) + (CH ^ '0'), CH = getchar();
    return A * FL;
}
void ot(int x)
{
    if(x < 0)
        putchar('-'), x = -x;
    if(x >= 10)
        ot(x / 10);
    putchar((x % 10) | '0');
}
#define pc_ (putchar(' '))
#define pc_n (putchar('\n'))
const int CTR = 2e5 + 7;
int n;
vector<int> G[CTR];
int p, q;
int dis[CTR];
void dfs1(int x, int f)
{
    dis[x] = dis[f] + 1;
    (dis[x] > dis[p]) && (p = x);
    for(re v : G[x]) if(v != f) dfs1(v, x);
}
bool fl[CTR];
void dfs2(int x, int f)
{
    if(x == q) fl[x] = 1;
    for(re v : G[x]) if(v != f) dfs2(v, x), fl[x] |= fl[v];
}
int tot;
int ans[CTR];
void dfs3(int x, int f)
{
    ans[x] = ++tot;
    for(re v : G[x]) if(v != f && !fl[v]) dfs3(v, x), ans[x] = ++tot;
    for(re v : G[x]) if(v != f && fl[v]) dfs3(v, x);
}
Bessie main()
{
    n = read();
    for(re i = 1, u, v; i < n; ++i)
        u = read(), v = read(), G[u].push_back(v), G[v].push_back(u);
    dfs1(1, 0);
    q = p;
    dfs1(p, 0);
    dfs2(p, 0);
    dfs3(p, 0);
    for(re i = 1; i <= n; ++i) ot(ans[i]),pc_;
    return 0;
}