fork download 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. using namespace std;
  4.  
  5. const int N = 100005;
  6.  
  7. struct Edge {
  8.     int v;
  9.     ll w;
  10. };
  11.  
  12. vector<Edge> adj[N];
  13.  
  14. ll down_dp[N];
  15. ll up_dp[N];
  16. ll ans[N];
  17.  
  18. void dfs1(int u, int p) {
  19.     down_dp[u] = 0;
  20.  
  21.     for (auto e : adj[u]) {
  22.         int v = e.v;
  23.         ll w = e.w;
  24.  
  25.         if (v == p) continue;
  26.  
  27.         dfs1(v, u);
  28.  
  29.         down_dp[u] = max(down_dp[u], down_dp[v] + w);
  30.     }
  31. }
  32.  
  33. void dfs2(int u, int p) {
  34.     ll mx1 = -1, mx2 = -1;
  35.  
  36.     for (auto e : adj[u]) {
  37.         int v = e.v;
  38.         ll w = e.w;
  39.  
  40.         if (v == p) continue;
  41.  
  42.         ll cur = down_dp[v] + w;
  43.  
  44.         if (cur > mx1) {
  45.             mx2 = mx1;
  46.             mx1 = cur;
  47.         }
  48.         else if (cur > mx2) {
  49.             mx2 = cur;
  50.         }
  51.     }
  52.  
  53.     for (auto e : adj[u]) {
  54.         int v = e.v;
  55.         ll w = e.w;
  56.  
  57.         if (v == p) continue;
  58.  
  59.         ll cur = down_dp[v] + w;
  60.  
  61.         ll use = mx1;
  62.  
  63.         if (cur == mx1) use = mx2;
  64.  
  65.         up_dp[v] = w + max(up_dp[u], max(0LL, use));
  66.  
  67.         dfs2(v, u);
  68.     }
  69. }
  70.  
  71. int main() {
  72.     ios::sync_with_stdio(false);
  73.     cin.tie(nullptr);
  74.  
  75.     freopen("DOG.INP", "r", stdin);
  76.     freopen("DOG.OUT", "w", stdout);
  77.  
  78.     int n;
  79.     cin >> n;
  80.  
  81.     for (int i = 1; i < n; i++) {
  82.         int u, v;
  83.         ll c;
  84.         cin >> u >> v >> c;
  85.  
  86.         adj[u].push_back({v, c});
  87.         adj[v].push_back({u, c});
  88.     }
  89.  
  90.     dfs1(1, 0);
  91.  
  92.     up_dp[1] = 0;
  93.     dfs2(1, 0);
  94.  
  95.     for (int i = 1; i <= n; i++) {
  96.         ans[i] = max(down_dp[i], up_dp[i]);
  97.         cout << ans[i] << '\n';
  98.     }
  99.  
  100.     return 0;
  101. }
Success #stdin #stdout 0.01s 7900KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/08tABI
language:
C++14 (clang 8.0)
created:
5 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!