代码是拷贝其他人的 附链接：https://blog.csdn.net/the_ZED/article/details/104174375?utm_medium=distribute.pc_relevant_t0.none-task-blog-BlogCommendFromMachineLearnPai2-1.compare&depth_1-utm_source=distribute.pc_relevant_t0.none-task-blog-BlogCommendFromMachineLearnPai2-1.compare
思路：根据边的权值直接求图的直径？ 求直径的算法：任选一点，求最远的点 在以最远的点求最远的点，这俩点就是直径
#include <iostream> #include <cmath> #include <algorithm> #include <cstdlib> #include <string> #include <cstring> #include <vector> using namespace std; const int maxn = 1e5 + 5; int maxFarNode; int maxlen = -1; bool vis[maxn]; struct Node { int child, length; Node(int a, int b) { child = a, length = b; } }; vector<Node> v[maxn]; void dfs(int node, int nowlen) { if (vis[node]) return ; vis[node] = true; //遍历node的后继节点 for (int i = 0; i < v[node].size(); i++) { int child = v[node][i].child; int length = v[node][i].length; if (vis[child]) continue; if (nowlen + length > maxlen) { maxlen = nowlen + length; maxFarNode = child; } dfs(child, nowlen + length); } } int main() { int n; cin >> n; for (int i = 1; i < n; i++) { int x, y, len; cin >> x >> y >> len; v[x].push_back(Node(y, len)); v[y].push_back(Node(x, len)); } dfs(1, 0); memset(vis, false, sizeof(vis)); maxlen = -1; dfs(maxFarNode, 0); cout << maxlen * 10 + maxlen * (maxlen + 1) /2 << endl; system("pause"); return 0; }