题解：AT_abc428_e [ABC428E] Farthest Vertex

题意简述

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

解题思路

~~很简单的一个换根 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

的转移即可）。

代码

CPP

#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。

题解：AT_abc428_e [ABC428E] Farthest Vertex

文章操作

题意简述

解题思路

代码

相关推荐

评论

题解：AT_abc428_e [ABC428E] Farthest Vertex