当时卡在了次大值这个理解的地方,感觉好巧 - 这个题目能够和第一题一样的方式求解down的次大值的原因好巧
注意第一题那样的方法求解的次大值是不经过最大值节点的最大值,而不是真正的从这个点向下走的次大值,但是在up的时候刚好需要的就是这样的次大值,因为如果父节点向下的最大路径经过了当前子节点,那么当前子节点的up就需要父节点不经过当前子节点的最大值,也就是按照第一题的方法求解的次大值
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
inline int sd(int &n) { return scanf("%d", &n); }
inline int sld(ll &n) { return scanf("%lld", &n); }
const int inf = 0x3f3f3f3f;
const int maxn = 1e6+ 6;
int h[maxn], e[maxn], w[maxn], ne[maxn], idx;
int d1[maxn], d2[maxn], p1[maxn], p2[maxn];
int up[maxn];
void add(int a, int b, int c){
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
int dfs_d(int u, int fa){
d1[u] = d2[u] = -inf;
for(int i = h[u];i != -1;i = ne[i]){
int j = e[i];
if(j == fa) continue;
int d = dfs_d(j, u) + w[i];
if(d >= d1[u]){
d2[u] = d1[u];
d1[u] = d;
p2[u] = p1[u];
p1[u] = j;
}else if(d > d2[u]){
d2[u] = d;
p2[u] = j;
}
}
if(d1[u] == -inf) d1[u] = d2[u] = 0;
return d1[u];
}
void dfs_u(int u, int fa){
for(int i = h[u];i != -1;i = ne[i]){
int j = e[i];
if(j == fa) continue;
if(p1[u] == j) up[j] = max(up[u], d2[u]) + w[i];
else up[j] = max(up[u], d1[u]) + w[i];
dfs_u(j, u);
}
}
int main(){
int n; sd(n);
memset(h, -1, sizeof h);
for(int i = 1;i < n;++i){
int a, b, c; sd(a), sd(b), sd(c);
add(a, b, c), add(b, a, c);
}
dfs_d(1, -1);
dfs_u(1, -1);
int ans = inf;
for(int i = 1;i <= n;++i) ans = min(ans, max(up[i], d1[i]));
cout << ans << endl;
return 0;
}
太强了