题解：AT_abc428_e [ABC428E] Farthest Vertex

Chiesl · 2025-10-19 16:39:13 · 题解

题意简述

给定一棵无根树，对于每个节点，求与其距离最远的节点中最大的编号。

解题思路

很简单的一个换根 dp 板子，秒了。

对于这种要求每个节点答案的，优先考虑换根 dp。

以下的讨论中只考虑距离，编号在具体实现时只需要用 pair 维护即可。

令节点 1 为根节点，设 f_u 表示以 u 为根的子树中与其距离最大的节点与 u 的距离，显然有以下转移：

• f_u = \max\limits_{v \in son_u}\{f_v\} + 1

然后考虑换根，我们设 g_u 表示整棵树中与节点 u 距离最远的节点与 u 的距离。

• g_u = \max(f_u, g_{fa_u} + 1)

我们发现，当与 fa_u 距离最大的节点在 u 的子树当中，刚刚的转移方程并不成立。

此时只需要多维护一个距离的次大值 sec 就可以处理这种情况了，具体而言：

当 g_{fa_u} 所代表的节点不属于以 u 为根的子树时：

• g_u = \max(f_u, g_{fa_u} + 1)

否则：

• g_u = \max(f_u, sec_{fa_u} + 1)

特殊的：

• g_1 = f_1

注意 sec_u 与 g_u 所代表的节点不能来源于 u 的同一个儿子的子树当中（在程序实现中，对于 v \in son_u，不考虑 sec_u 从 sec_v 的转移即可）。

代码

#include<bits/stdc++.h>
#define PII pair<int, int>
#define mk make_pair
using namespace std;
const int N = 5e5 + 5;
int n, dep[N];
vector<int> e[N];
PII f[N], sec[N];
void dfs1 (int u, int fa) {
    dep[u] = dep[fa] + 1, f[u] = mk(0, u), sec[u] = mk(-1, -1);
    for (int v : e[u]) {
        if (v != fa) {
            dfs1(v, u);
            PII tmp = mk(f[v].first + 1, f[v].second);
            if (tmp.first > f[u].first || (tmp.first == f[u].first && tmp.second > f[u].second)) sec[u] = f[u], f[u] = tmp;
            else if (tmp.first > sec[u].first || (tmp.first == sec[u].first && tmp.second > sec[u].second)) sec[u] = tmp;
        }
    }
}
void dfs2 (int u, int fa) {
    for (int v : e[u]) {
        if (v == fa) continue;
        PII tmp = mk(f[u].first + 1, f[u].second);
        if (f[u].second == f[v].second) tmp = mk(sec[u].first + 1, sec[u].second);
        if (tmp.first > f[v].first || (tmp.first == f[v].first && tmp.second > f[v].second)) sec[v] = f[v], f[v] = tmp;
        else if (tmp.first > sec[v].first || (tmp.first == sec[v].first && tmp.second > sec[v].second)) sec[v] = tmp;
        dfs2(v, u);
    }
}
int main () {
    scanf("%d", &n);
    for (int i = 1, u, v; i < n; i++) {
        scanf("%d%d", &u, &v);
        e[u].push_back(v), e[v].push_back(u);
    }
    dfs1(1, 0), dfs2(1, 0);
    for (int i = 1; i <= n; i++) printf("%d\n", f[i].second);
    return 0;
}

时间复杂度：\operatorname{O}(n)。

这是蒟蒻第一次 abc 1525 分，特发一篇题解纪念场切 e 题。

感谢管理员神犇耐心看完，求过 qwq。