P10725

MARSandEARTH · 2024-07-17 09:35:00 · 题解

6 月份 GESP 原题，赛时过了。

前置知识

树上 BFS。

题目大意

有⼀棵包含 n 个节点的树，这棵树上的任意⼀个节点有白黑两种颜色。

求相距最远的一对不同颜色节点的距离是多少。

思路

既然题目说了求最远不同颜色点对，那么就必定是一黑一白废话。所以我们可以先假定一点为根节点，分别用 BFS 寻找距离该点最远的白点与黑点，然后分别用 BFS 寻找最远的不同颜色节点，最后两个距离取最大值即可。时间复杂度 O(n)。

代码太长了，就不放了，还请读者自行写出。