#1191150 (C++23(gcc16)) No.3755 Root for Your Route

• 問題: No.3755 Root for Your Route
• ユーザー: ei1333333
• 提出日時: 2026-10-02 22:08:55
• 言語: C++23(gcc16) (gcc 16.1.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 188 ms / 3,000 ms
• コード長: 9,235 bytes
• コンパイル時間: 4,460 ms
• コンパイル使用メモリ: 405,104 KB
• 実行使用メモリ: 63,632 KB
• 最終ジャッジ日時: 2026-10-02 22:09:12
• 合計ジャッジ時間: 11,683 ms
• ジャッジサーバーID （参考情報）: judge4_0 / judge2_0

ファイルパターン	結果
sample	AC * 1
other	AC * 39

ソースコード

#line 1 "template/template.hpp"
#include <bits/stdc++.h>

#if __has_include(<atcoder/all>)
#include <atcoder/all>

#endif

using namespace std;

using int64 = long long;

const int64 infll = (1LL << 62) - 1;
const int inf = (1 << 30) - 1;

struct IoSetup {
  IoSetup() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);
    cerr << fixed << setprecision(10);
  }
} iosetup;

template<typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p) {
  os << p.first << " " << p.second;
  return os;
}

template<typename T1, typename T2>
istream &operator>>(istream &is, pair<T1, T2> &p) {
  is >> p.first >> p.second;
  return is;
}

template<typename T>
ostream &operator<<(ostream &os, const vector<T> &v) {
  for (size_t i = 0; i < v.size(); i++) {
    os << v[i] << (i + 1 != v.size() ? " " : "");
  }
  return os;
}

template<typename T>
istream &operator>>(istream &is, vector<T> &v) {
  for (T &in: v) is >> in;
  return is;
}

template<typename T1, typename T2>
bool chmax(T1 &a, T2 b) {
  return a < b && (a = b, true);
}

template<typename T1, typename T2>
bool chmin(T1 &a, T2 b) {
  return a > b && (a = b, true);
}

template<typename T = int64>
vector<T> make_v(size_t a) {
  return vector<T>(a);
}

template<typename T, typename... Ts>
auto make_v(size_t a, Ts... ts) {
  return vector<decltype(make_v<T>(ts...))>(a, make_v<T>(ts...));
}

template<typename T, typename V>
enable_if_t<is_class_v<T> == 0> fill_v(T &t, const V &v) {
  t = v;
}

template<typename T, typename V>
enable_if_t<is_class_v<T> != 0> fill_v(T &t, const V &v) {
  for (auto &e: t) fill_v(e, v);
}

template<typename F>
struct FixPoint : F {
  explicit FixPoint(F &&f) : F(std::forward<F>(f)) {
  }

  template<typename... Args>
  decltype(auto) operator()(Args &&... args) const {
    return F::operator()(*this, std::forward<Args>(args)...);
  }
};

template<typename F>
decltype(auto) MFP(F &&f) {
  return FixPoint<F>{std::forward<F>(f)};
}

#line 2 "graph/tree/centroid-decomposition.hpp"

#include <vector>

#line 2 "graph/graph-template.hpp"

#include <cstddef>
#include <iostream>
#line 6 "graph/graph-template.hpp"

template<typename T = int>
struct Edge {
  int from, to;
  T cost;
  int idx;

  Edge() = default;

  Edge(int from, int to, T cost = 1, int idx = -1)
    : from(from), to(to), cost(cost), idx(idx) {
  }

  operator int() const { return to; }
};

template<typename T = int>
struct Graph {
  std::vector<std::vector<Edge<T> > > g;
  int es;

  Graph() = default;

  explicit Graph(int n) : g(n), es(0) {
  }

  std::size_t size() const { return g.size(); }

  void add_directed_edge(int from, int to, T cost = 1) {
    g[from].emplace_back(from, to, cost, es++);
  }

  void add_edge(int from, int to, T cost = 1) {
    g[from].emplace_back(from, to, cost, es);
    g[to].emplace_back(to, from, cost, es++);
  }

  void read(int M, int padding = -1, bool weighted = false,
            bool directed = false) {
    for (int i = 0; i < M; i++) {
      int a, b;
      std::cin >> a >> b;
      a += padding;
      b += padding;
      T c = T(1);
      if (weighted) std::cin >> c;
      if (directed)
        add_directed_edge(a, b, c);
      else
        add_edge(a, b, c);
    }
  }

  inline std::vector<Edge<T> > &operator[](const int &k) { return g[k]; }

  inline const std::vector<Edge<T> > &operator[](const int &k) const {
    return g[k];
  }
};

template<typename T = int>
using Edges = std::vector<Edge<T> >;
#line 6 "graph/tree/centroid-decomposition.hpp"

/**
 * @brief Centroid-Decomposition(重心分解)
 */
template<typename T>
struct CentroidDecomposition : Graph<T> {
public:
  using Graph<T>::Graph;
  using Graph<T>::g;
  Graph<int> tree;

  int build(int t = 0) {
    sub.assign(g.size(), 0);
    v.assign(g.size(), 0);
    tree = Graph<int>(g.size());
    return build_dfs(0);
  }

  explicit CentroidDecomposition(const Graph<T> &g) : Graph<T>(g) {
  }

private:
  std::vector<int> sub;
  std::vector<int> v;

  inline int build_dfs(int idx, int par) {
    sub[idx] = 1;
    for (auto &to: g[idx]) {
      if (to == par || v[to]) continue;
      sub[idx] += build_dfs(to, idx);
    }
    return sub[idx];
  }

  inline int search_centroid(int idx, int par, const int mid) {
    for (auto &to: g[idx]) {
      if (to == par || v[to]) continue;
      if (sub[to] > mid) return search_centroid(to, idx, mid);
    }
    return idx;
  }

  inline int build_dfs(int idx) {
    int centroid = search_centroid(idx, -1, build_dfs(idx, -1) / 2);
    v[centroid] = true;
    for (auto &to: g[centroid]) {
      if (!v[to]) tree.add_directed_edge(centroid, build_dfs(to));
    }
    v[centroid] = false;
    return centroid;
  }
};

#line 2 "structure/convex-hull-trick/dynamic-li-chao-tree.hpp"

#include <algorithm>
#include <utility>

/**
 * @brief Dynamic-Li-Chao-Tree
 *
 */
template<typename T, T x_low, T x_high, T id>
struct DynamicLiChaoTree {
  struct Line {
    T a, b;

    Line(T a, T b) : a(a), b(b) {
    }

    inline T get(T x) const { return a * x + b; }
  };

  struct Node {
    Line x;
    Node *l, *r;

    Node(const Line &x) : x{x}, l{nullptr}, r{nullptr} {
    }
  };

  Node *root;

  DynamicLiChaoTree() : root{nullptr} {
  }

  Node *add_line(Node *t, Line &x, const T &l, const T &r, const T &x_l,
                 const T &x_r) {
    if (!t) return new Node(x);

    T t_l = t->x.get(l), t_r = t->x.get(r);

    if (t_l <= x_l && t_r <= x_r) {
      return t;
    } else if (t_l >= x_l && t_r >= x_r) {
      t->x = x;
      return t;
    } else {
      T m = (l + r) / 2;
      if (m == r) --m;
      T t_m = t->x.get(m), x_m = x.get(m);
      if (t_m > x_m) {
        std::swap(t->x, x);
        if (x_l >= t_l)
          t->l = add_line(t->l, x, l, m, t_l, t_m);
        else
          t->r = add_line(t->r, x, m + 1, r, t_m + x.a, t_r);
      } else {
        if (t_l >= x_l)
          t->l = add_line(t->l, x, l, m, x_l, x_m);
        else
          t->r = add_line(t->r, x, m + 1, r, x_m + x.a, x_r);
      }
      return t;
    }
  }

  void add_line(const T &a, const T &b) {
    Line x(a, b);
    root = add_line(root, x, x_low, x_high, x.get(x_low), x.get(x_high));
  }

  Node *add_segment(Node *t, Line &x, const T &a, const T &b, const T &l,
                    const T &r, const T &x_l, const T &x_r) {
    if (r < a || b < l) return t;
    if (a <= l && r <= b) {
      Line y{x};
      return add_line(t, y, l, r, x_l, x_r);
    }
    if (t) {
      T t_l = t->x.get(l), t_r = t->x.get(r);
      if (t_l <= x_l && t_r <= x_r) return t;
    } else {
      t = new Node(Line(0, id));
    }
    T m = (l + r) / 2;
    if (m == r) --m;
    T x_m = x.get(m);
    t->l = add_segment(t->l, x, a, b, l, m, x_l, x_m);
    t->r = add_segment(t->r, x, a, b, m + 1, r, x_m + x.a, x_r);
    return t;
  }

  void add_segment(const T &l, const T &r, const T &a, const T &b) {
    Line x(a, b);
    root = add_segment(root, x, l, r - 1, x_low, x_high, x.get(x_low),
                       x.get(x_high));
  }

  T query(const Node *t, const T &l, const T &r, const T &x) const {
    if (!t) return id;
    if (l == r) return t->x.get(x);
    T m = (l + r) / 2;
    if (m == r) --m;
    if (x <= m)
      return std::min(t->x.get(x), query(t->l, l, m, x));
    else
      return std::min(t->x.get(x), query(t->r, m + 1, r, x));
  }

  T query(const T &x) const { return query(root, x_low, x_high, x); }
};


int main() {
  // 直感的には重心分解して各頂点について最大値を求めれば良い

  int N;
  cin >> N;
  vector<int64> A(N);
  cin >> A;
  CentroidDecomposition<int> g(N);
  g.read(N - 1);
  auto root = g.build();
  vector<int> used(N);
  struct Node {
    int idx, par, dep;
    int64 sum;
  };
  auto ans = A;
  vector best(N, -infll);
  auto rec = MFP([&](auto rec, int centroid) -> void {
    used[centroid] = true;
    best[centroid] = -infll;
    vector<vector<Node> > chs;
    for (auto sub: g[centroid]) {
      if (used[sub]) continue;
      chs.emplace_back();
      auto dfs = MFP([&](auto dfs, int v, int par, int dep, int64 sum) -> void {
        chs.back().emplace_back( v, par, dep, sum - 1ll * dep * (dep + 1) / 2);
        best[v] = -infll;
        for (auto to: g[v]) {
          if (to == par or used[to]) continue;
          dfs(to, v, dep + 1, sum + A[to]);
        }
      });
      dfs(sub, centroid, 1, A[centroid] + A[sub]);
    }
    auto baka = [&] {
      DynamicLiChaoTree<int64, 0, 100000, infll> cht;
      cht.add_line(0, -A[centroid]);
      for (const auto& sub : chs) {
        for (auto& [v, par, dep, sum]: sub) {
          chmax(best[v], sum - A[centroid] - cht.query(dep));
        }
        for (auto& [v, par, dep, sum]: sub) {
          cht.add_line(dep, -sum);
        }
      }
    };
    baka();
    ranges::reverse(chs);
    baka();
    for (auto &vs: chs) {
      ranges::reverse(vs);
      for (auto& [v, par, dep, sum]: vs) {
        chmax(ans[v], best[v]);
        chmax(ans[centroid], best[v]);
        if (par != centroid) {
          chmax(best[par], best[v]);
        }
      }
    }
    for (auto to: g.tree[centroid]) {
      rec(to);
    }
    used[centroid] = false;
  });
  rec(root);
  cout << *ranges::min_element(ans) << endl;
}