题解 [牛客OI周赛15-提高组A] 环球旅行
环球旅行
https://ac.nowcoder.com/acm/contest/4912/A
题目描述
给定一棵大小为 的树,让你断一条边,使得树上距离最大值最小。
正解
先求出树直径的两个端点 ,
,最后断的边肯定是直径上的边。
考虑枚举这条边,然后快速统计答案。
先可以预处理出直径这一条链,然后求出链上前缀的直径和后缀的直径就可以 统计答案了。
断掉直径上的边后,两边联通块的直径肯定分别是 (考虑树直径的性质,反证法可以证明)。
那么好办,对于直径上的每一个点,求出它挂出去的链的最远距离即可。
时间复杂度 。
出题人不给大样例还得自己打对拍,差评。
#include <bits/stdc++.h> #define N 1000005 #define inf 1000000005 using namespace std; int n, rt1, rt2; int head[N], nex[N << 1], to[N << 1], eVal[N << 1], ecnt; int mDist[N], f[N], g[N]; bool inList[N]; vector<int> arr; inline int read() { int x = 0; char ch = getchar(); while(!isdigit(ch)) ch = getchar(); while(isdigit(ch)) x = x * 10 + ch - '0', ch = getchar(); return x; } inline void addE(int u, int v, int w) { to[++ecnt] = v, eVal[ecnt] = w; nex[ecnt] = head[u], head[u] = ecnt; } int que[N], dist[N], pre[N]; void getr(int s, int &rt) { rt = 0, dist[0] = -1; int hd = 0, tl = -1, u, v; for(int i = 1; i <= n; ++i) dist[i] = inf; dist[s] = 0, que[++tl] = s; while(hd <= tl) { u = que[hd++]; if(dist[u] > dist[rt]) rt = u; for(int i = head[u]; i; i = nex[i]) { v = to[i]; if(dist[v] > dist[u] + eVal[i]) { dist[v] = dist[u] + eVal[i]; pre[v] = u, que[++tl] = v; } } } } void getList() { getr(1, rt1); getr(rt1, rt2); int u = rt2; inList[u] = true; arr.push_back(u); while(u != rt1) { u = pre[u]; inList[u] = true; arr.push_back(u); } reverse(arr.begin(), arr.end()); } void getDist(int s) { int hd = 0, tl = -1, u, v; que[++tl] = s; while(hd <= tl) { u = que[hd++]; mDist[s] = max(mDist[s], dist[u]); for(int i = head[u]; i; i = nex[i]) { v = to[i]; if(dist[v] > dist[u] + eVal[i]) { dist[v] = dist[u] + eVal[i]; que[++tl] = v; } } } } int main() { n = read(); for(int i = 1, u, v, w; i < n; ++i) { u = read(), v = read(), w = read(); addE(u, v, w), addE(v, u, w); } getList(); for(int i = 1; i <= n; ++i) dist[i] = inf; for(auto u : arr) dist[u] = 0; for(auto u : arr) getDist(u); getr(rt1, rt2); // 重新得到距离 for(int i = 0, u; i < arr.size(); ++i) { u = arr[i]; f[i] = dist[u] + mDist[u]; if(i) f[i] = max(f[i], f[i - 1]); } for(int i = arr.size() - 1, u; ~i; --i) { u = arr[i]; g[i] = dist[rt2] - dist[u] + mDist[u]; if(i != arr.size() - 1) g[i] = max(g[i], g[i + 1]); } int ans = inf; for(int i = 0; i < arr.size() - 1; ++i) ans = min(ans, max(f[i], g[i + 1])); printf("%d\n", ans); return 0; }