齐心抗疫(找树的直径)

题意: 给你一颗n个点的树,树上每个点有一个值,树上每条边长度为1,对于两点x,y之间的代价,x对y的代价可以表示为a[x]*(dis(x,y)),要求任选两点,获得一个最大的价值。 数据范围:n<=50000。 思路: 直接遍历每个点,找距离他最远的点,然后维护最大值 。这个方法只能骗部分分,因为时间复杂度为O(n^2)。 先讲结论: 我们假设这棵树中距离最大的两个点的距离为dismax,这两个点之间的距离称为树的直径,那么对于任何一个点,他在树上距离他最远的点必然是直径的两个端点之一。至于怎么证明,自己思考比较好。我讲的不是很清楚。 找树的直径: 我们先随意以一个点为根,找到离他最远