Advertisement
pb_jiang

ABC222F WA2

Jan 19th, 2023
107
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.84 KB | None | 0 0
  1. // Problem: F - Expensive Expense
  2. // Contest: AtCoder - Exawizards Programming Contest 2021(AtCoder Beginner Contest 222)
  3. // URL: https://atcoder.jp/contests/abc222/tasks/abc222_f
  4. // Memory Limit: 1024 MB
  5. // Time Limit: 4000 ms
  6. //
  7. // Powered by CP Editor (https://cpeditor.org)
  8.  
  9. #include <assert.h>
  10. #include <bits/stdc++.h>
  11. using namespace std;
  12. #define dbg(...) logger(#__VA_ARGS__, __VA_ARGS__)
  13. template <typename... Args> void logger(string vars, Args &&... values)
  14. {
  15.     cerr << vars << " = ";
  16.     string delim = "";
  17.     (..., (cerr << delim << values, delim = ", "));
  18.     cerr << endl;
  19. }
  20.  
  21. template <class T> inline auto vv(int m) { return vector<vector<T>>(m, vector<T>(m)); }
  22. template <class T> inline auto vv(int m, int n) { return vector<vector<T>>(m, vector<T>(n)); }
  23. template <class T, T init> inline auto vv(int m) { return vector<vector<T>>(m, vector<T>(m, init)); }
  24. template <class T, T init> inline auto vv(int m, int n) { return vector<vector<T>>(m, vector<T>(n, init)); }
  25.  
  26. template <class T> using mpq = priority_queue<T, vector<T>, greater<T>>;
  27.  
  28. using ll = long long;
  29. using pii = pair<int, int>;
  30. using pll = pair<ll, ll>;
  31. using p4l = pair<pll, pll>;
  32. using vl = vector<ll>;
  33. using vi = vector<int>;
  34.  
  35. int n;
  36. map<pll, ll> ew;
  37. vl vw;
  38. vl g[200003];
  39. vl ans;
  40. vector<pll> top1, top2;
  41.  
  42. pll dfs(ll u, ll fa)
  43. {
  44.     auto &a = top1[u], &b = top2[u];
  45.     a = b = {vw[u], u};
  46.  
  47.     for (auto v : g[u]) {
  48.         if (v == fa)
  49.             continue;
  50.         auto [weight, end_vid] = dfs(v, u);
  51.         pll key = {min(u, v), max(u, v)};
  52.         ll new_weight = ew[key] + weight;
  53.         if (a.first < new_weight) {
  54.             b = a;
  55.             a.first = new_weight;
  56.             a.second = v;
  57.         } else if (b.first < new_weight) {
  58.             b.first = new_weight;
  59.             b.second = v;
  60.         }
  61.     }
  62.     return a;
  63. }
  64.  
  65. void dfs2(ll u, ll fa, ll lp)
  66. {
  67.     ans[u] = max(lp, top1[u].first);
  68.     // ans[end] = max(ans[end], lp + vw[u]);
  69.     for (auto v : g[u]) {
  70.         if (v == fa)
  71.             continue;
  72.         pll key = {min(u, v), max(u, v)};
  73.         ll uv_dist = ew[key];
  74.         ll this_lp = 0;
  75.         if (top1[u].second == v) {
  76.             this_lp = max(this_lp, top2[u].second + (top2[u].second == v ? -1 : 1) * uv_dist);
  77.         } else {
  78.             this_lp = max(this_lp, top1[u].second + uv_dist);
  79.         }
  80.         dfs2(v, u, this_lp);
  81.     }
  82. }
  83.  
  84. int main(int argc, char **argv)
  85. {
  86.     cin >> n;
  87.     vw = vl(n + 1);
  88.     ans = vl(n + 1);
  89.     top1 = top2 = vector<pll>(n + 1);
  90.     ll a, b, c;
  91.     for (int i = 1; i < n; ++i)
  92.         cin >> a >> b >> c, g[a].push_back(b), g[b].push_back(a), ew[{min(a, b), max(a, b)}] = c;
  93.     for (int i = 1; i <= n; ++i)
  94.         cin >> vw[i];
  95.  
  96.     dfs(1, -1);
  97.     dfs2(1, -1, 0);
  98.     for (int i = 1; i <= n; ++i)
  99.         cout << ans[i] << '\n';
  100.     return 0;
  101. };
  102.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement