[ARC117D] Miracle Tree

标签：ARC117D EndPoint dist int Tree Miracle fa cal operatorname

题目大意

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

1. 所有 \(E_i\ge 1(1\le i\le n)\)。
2. 对于任意一组 \((i,j)(1 ≤ i < j ≤ N)\)，使 \(|E_i-E_j|\geq \operatorname{dist}(i,j)\)，\(\operatorname{dist}(i,j)\) 即树上 \(i\) 和 \(j\) 两点距离。
3. 使 \(E\) 中的最大值最小。

思路

首先只考虑前两个限制，设有点 \(i,j,k\) 满足

\[E_i < E_j < E_k \]

因为有

\[E_k-E_i=E_k-E_j+E_j-E_i \]

由于

\[E_k-E_j\geq \operatorname{dist}(k,j),E_j-E_i\geq \operatorname{dist}(i,j) \]

所以有

\[E_k-E_i \geq \operatorname{dist}(k,j) + \operatorname{dist}(i,j) \]

又因为

\[\operatorname{dist}(k,j) + \operatorname{dist}(i,j) \geq \operatorname{dist}(i,k) \]

使得 \(E_k-E_j\) 尽可能小，得到

\[E_k-E_i=\operatorname{dist}(k,i) \]

那么我们直接可以用欧拉序列进行构造，欧拉序列的长度为 \(2n - 1\)。

再考虑第三个限制条件，让 \(E\) 中的最大值最小。

考虑我们欧拉序列有重复走的部分，我们使那个重复走的链的部分最短，那么那一段我们就可以选取树的直径。

那么我们怎么保证固定我们最后走哪个点呢？如果一条边在直径上，我们就最后经过这条边，这样在到达直径的第二个端点时，能够保证其他的点都已经遍历过。

Code

#include <bits/stdc++.h>

using namespace std;

const int N = 200500;

vector<int> e[N];

int n;

int dis[N];

int EndPoint,End;

void dfs1(int x,int fa) {
    dis[x] = dis[fa] + 1;

    if(dis[x] > dis[EndPoint])
        EndPoint = x;
    
    for(auto const &to : e[x]) {
        if(to == fa)
            continue;
        
        dfs1(to,x);
    }
}

void GetCal() {
    dfs1(1,0);

    End = EndPoint;

    dfs1(EndPoint,0);
}

bool cal[N];

void dfs2(int x,int fa) {
    if(x == End)
        cal[x] = 1;
    for(auto const &to : e[x]) {
        if(to == fa)
            continue;
        
        dfs2(to,x);
        cal[x] |= cal[to];
    }
}

int ans[N],tot;

void dfs3(int x,int fa) {
    tot ++;
    ans[x] = tot;

    for(auto const &to : e[x]) {
        if(to == fa || cal[to])
            continue;
        
        dfs3(to,x);
        tot ++;
    }

    for(auto const &to : e[x]) {
        if(to == fa || !cal[to])
            continue;
        
        dfs3(to,x);
    }
}

int main() {
    cin >> n;

    for(int i = 1,u,v;i < n; i++) {
        cin >> u >> v;
        e[u].emplace_back(v);
        e[v].emplace_back(u);
    }

    GetCal();
    
    dfs2(EndPoint,0);
    dfs3(EndPoint,0);

    for(int i = 1;i <= n; i++) 
        cout << ans[i] << " ";
    
    cout << "\n";
    return 0;
}

标签：ARC117D,EndPoint,dist,int,Tree,Miracle,fa,cal,operatorname
From： https://www.cnblogs.com/baijian0212/p/ARC117D.html