首页 > 代码库 > XTOJ 1267：Highway（树的直径）***
XTOJ 1267：Highway（树的直径）***
http://202.197.224.59/OnlineJudge2/index.php/Problem/read/id/1267
题意：给出一棵树，每条树边有权值，现在要修建n-1条边，边的权值为边的两点间原来的树边权值之和，问最大能是多少。
思路：背锅题。比赛的时候想过树的直径，可是想歪了。后面队友想到的解法是对每个叶子和每个结点连边，结果MLE了。
没有想到：把树的直径确定之后，对于每一个点，能跑到的最远距离就是到两个端点的较远的点的距离。
因此可以先dfs跑到一个端点，再dfs跑到另一个端点（顺便处理出第一个距离数组），再dfs从一个另一个端点跑回去（处理出第二个距离数组）。
因为最大的长度只能算一次（n-1条边），因此要减去一次。
要I64d（比赛的时候可以lld，现在却不行）
1 #include <bits/stdc++.h> 2 using namespace std; 3 typedef long long LL; 4 #define N 100010 5 struct Edge { 6 int v, nxt; LL w; 7 Edge () {} 8 Edge (int v, int nxt, LL w) : v(v), nxt(nxt), w(w) {} 9 } edge[N*2];10 int head[N], tot, n, p;11 LL dis[2][N], big;12 13 void Add(int u, int v, LL w) {14 edge[tot] = Edge(v, head[u], w); head[u] = tot++;15 edge[tot] = Edge(u, head[v], w); head[v] = tot++;16 }17 18 void dfs(int u, int fa, int k) {19 if(dis[k][u] > big) p = u, big = dis[k][u];20 for(int i = head[u]; ~i; i = edge[i].nxt) {21 int v = edge[i].v; if(v == fa) continue;22 dis[k][v] = edge[i].w + dis[k][u];23 dfs(v, u, k);24 }25 }26 27 int main() {28 while(~scanf("%d", &n)) {29 memset(head, -1, sizeof(head)); tot = 0;30 for(int i = 1; i < n; i++) {31 int u, v; LL w; scanf("%d%d%I64d", &u, &v, &w);32 Add(u, v, w);33 }34 dis[0][1] = 0, big = 0;35 dfs(1, -1, 0); // 从1找某个端点36 int l = p;37 38 dis[0][l] = 0, big = 0;39 dfs(l, -1, 0); // 从一个端点找另一个端点更新dis140 int r = p;41 42 dis[1][r] = 0;43 dfs(r, -1, 1); // 从另一个端点找回去更新dis244 45 LL ans = 0, now, res = 0;46 for(int i = 1; i <= n; i++)47 ans += max(dis[0][i], dis[1][i]);48 printf("%I64d\n", ans - dis[0][r]);49 }50 return 0;51 }
XTOJ 1267：Highway（树的直径）***
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。