[GESP202406 八级] 最远点对
GESP编程共123题，本题是整站第1424题，已经有人完成了本题，加油！
题目描述
小杨有⼀棵包含 n 个节点的树，这棵树上的任意⼀个节点要么是白色，要么是黑色。
小杨想知道相距最远的一对不同颜色节点的距离是多少。
输入格式
第一行包含⼀个正整数 n，代表树的节点数。
第二行包含 n 个非负整数 a1,a2,⋯,an（对于所有的 1≤i≤n，均有 ai 等于 0 或 1），其中如果 ai=0，则节点 i 的颜色为白色；如果 ai=1，则节点 i 的颜色为黑色。
之后 (n−1) 行，每行包含两个正整数 xi,yi，代表存在一条连接节点 xi 和 yi 的边。
保证输入的树中存在不同颜色的点。
输出格式
输出⼀个整数，代表相距最远的一对不同颜色节点的距离。
输入输出样例
输入 #1
5 0 1 0 1 0 1 2 1 3 3 4 3 5
输出 #1
3
说明/提示
样例解释
相距最远的不同颜色的一对节点为节点 2 和 5。
数据范围
本题采用捆绑测试。
| 子任务编号 | 得分 | n | ai | 特殊条件 |
|---|---|---|---|---|
| 1 | 30 | ≤10^5 | 0≤ai≤1 | 树的形态为一条链 |
| 2 | 30 | ≤10^3 | 0≤ai≤1 | |
| 3 | 40 | ≤10^5 | 0≤ai≤1 |
对于全部数据，保证有 1≤n≤10^5，0≤ai≤1。
别灰心，再试一次！
真题解析
【题目大意】
这是一个树结构，从树中选2个颜色不同的点，颜色分为黑色和白色。求最远的距离。分析样例。1、先建立树；2、选2个颜色不同的点，求最远距离。例如1是白色，2是黑色，距离是1.通过枚举，发现2是黑色，5是白色，距离是3，是答案。
【考纲知识点】
建树知识，深搜知识
【解题思路】
每个结点要么黑色要么白色，需要保存结点的颜色信息。选2个颜色不同的点，可以先枚举第1个点和第2个点，求他们的距离，再求最大值。任意2点都是连通的，能够相互访问，能求出最大值。根据数据范围，能得到部分分。另一种思路就是根据树的性质，答案的2个点假设是a和b，路径会经过他们的公共祖先，距离=公共祖先到a的距离+公共祖先到b的距离。每个点视为公共祖先的话，有可能是左孩子的黑色和右孩子的白色组合，也可能是左孩子的白色和右孩子的黑色组成，也可能只在左孩子或者右孩子中。所以，每个结点应该保留2种颜色的最远值。一次深搜即可。每个点访问1次，时间复杂度是O(n)。
参考程序
本站题目仅供学习，GESP版权归CCF所有，如有侵权请联系删除。站长陈老师QQ及微信:208234。