题解：AT_abc428_e [ABC428E] Farthest Vertex

· · 题解

给出一种比较暴力的解法吧。

首先我们发现每个点距离最大的点就是以那个点为根时的最大深度的点。

那么我们可以先暴力求出以一为根时，所有点的深度。

然后我们发现，如果原本以 u 为根的点的深度，若要将它转为 u 的儿子 v 的点的深度，那么 v 子树内的点的深度都减一，其余点的深度加一。

你可以想象一下，原本是 u 为根，然后将他的儿子 v 提根，相当于折一下，然后就是符合上述情况的。

然后又因为子树内的 dfn 序是连续的，于是我们可以第一遍遍历时先将以一为根所有点的深度和 dfn 求出来，然后用一个线段树维护每个点的深度值，第二遍遍历，每次要走到儿子的时候，就将深度值更新为以儿子为根时的深度值，然后答案就是以那个点为根时的最大深度值所在的最大点。

注意，要求的不是最大距离，而是其所在点，这里我在线段树上用了一个 pos 维护。

code

#include <bits/stdc++.h>
#define pb push_back
using namespace std;

const int N = 5e5 + 10;

vector <int> g[N];

int n, cnt, dep[N], dfn[N], mxdfn[N], id[N], ans[N];

struct SegmentTree {
    int t[N << 2], pos[N << 2], tag[N << 2];

    #define ls (p << 1)
    #define rs (p << 1 | 1)
    #define mid ((l + r) >> 1)

    inline void pushup (int p) {
        t[p] = max (t[ls], t[rs]);
        if (t[ls] == t[rs]) pos[p] = max (pos[ls], pos[rs]);
        else pos[p] = (t[ls] > t[rs] ? pos[ls] : pos[rs]);
    }

    inline void pushdown (int p) {
        if (tag[p]) t[ls] += tag[p], t[rs] += tag[p], tag[ls] += tag[p], tag[rs] += tag[p], tag[p] = 0;
    }

    void build (int p, int l, int r) {
        if (l == r) return t[p] = dep[id[l]], pos[p] = id[l], void ();
        build (ls, l, mid), build (rs, mid + 1, r), pushup (p);
    }

    void update (int p, int l, int r, int L, int R, int k) {
        if (L > R) return; 
        if (L <= l and r <= R) return t[p] += k, tag[p] += k, void ();
        pushdown (p);
        if (L <= mid) update (ls, l, mid, L, R, k);
        if (R > mid) update (rs, mid + 1, r, L, R, k);
        pushup (p);
    }
} seg;

void dfs1 (int u, int fa) {
    dep[u] = dep[fa] + 1, dfn[u] = mxdfn[u] = ++cnt, id[cnt] = u;
    for (int v : g[u])
        if (v != fa) dfs1 (v, u), mxdfn[u] = max (mxdfn[u], mxdfn[v]);
}

void dfs2 (int u, int fa) {
    ans[u] = seg.pos[1];
    for (int v : g[u]) 
        if (v != fa) {
            seg.update (1, 1, n, dfn[v], mxdfn[v], -1);
            seg.update (1, 1, n, 1, dfn[v] - 1, 1);
            seg.update (1, 1, n, mxdfn[v] + 1, n, 1);
            dfs2 (v, u);
            seg.update (1, 1, n, dfn[v], mxdfn[v], 1);
            seg.update (1, 1, n, 1, dfn[v] - 1, -1);
            seg.update (1, 1, n, mxdfn[v] + 1, n, -1); 
        }
}

int main () {
    cin >> n;
    for (int i = 1, u, v; i < n; i++) cin >> u >> v, g[u].pb (v), g[v].pb (u); 
    dfs1 (1, 0), seg.build (1, 1, n), dfs2 (1, 0);
    for (int i = 1; i <= n; i++) cout << ans[i] << endl;
    return 0;
}