nowcoder8.31D
题目大意：
给出一棵树，每个点有一个颜色，每次询问一对颜色，假设颜色为c1和c2，对于每次询问，输出颜色为c1的点到颜色为c2的点的最大距离。
n、q<=10^5
题解：
对于每个颜色，我们需要保存这个颜色的最远点对。
答案所在路径的两个端点必定分别属于两个不同颜色的最远点对。
证明比较显然，我们假设颜色c1的最远点对为(x1,y1)，颜色c2为(x2,y2)。
假设某一点z属于颜色c1，且它和x2的路径大于以上四个点两两之间的路径。
假设路径(x2,z)交路径(x2,x1)于u，那么显然有dis(u,z)>dis(u,x1)，那么z是绝对可以取代x1成为颜色c1的最远点对中的一点的，于原题设矛盾。
因此可以确定，没有这样的z。
版权声明：本文为lmlysklt原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。