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

题目描述 对于所有数据，满足2<=n<=50000，1<=a[i]<=1000。 题目思路 前言 本来我以为是最短路什么的。。。结果是我太菜，个人认为此题还是补充了自己知识，学到了不少 知识 树的直径表示最长的那段路径，显然可以任意点进行dfs求这一点到任意一点的最长距离，则那个点为直径的一个端点，然后在端点dfs找出最长距离，另一个点就是直径的另外一个端点。 正文 其实最后就三次dfs解决问题 代码 #include #include #include using