結果

問題 No.2654 [Cherry 6th Tune] Re: start! (Black Sheep)
ユーザー hashiryohashiryo
提出日時 2024-08-16 20:54:38
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 6,750 bytes
コンパイル時間 2,812 ms
コンパイル使用メモリ 219,196 KB
実行使用メモリ 22,584 KB
最終ジャッジ日時 2024-08-16 20:54:51
合計ジャッジ時間 12,913 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 TLE -
testcase_04 -- -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
testcase_32 -- -
testcase_33 -- -
testcase_34 -- -
testcase_35 -- -
testcase_36 -- -
testcase_37 -- -
testcase_38 -- -
testcase_39 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

// #define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
// clang-format off
std::ostream&operator<<(std::ostream&os,std::int8_t x){return os<<(int)x;}
std::ostream&operator<<(std::ostream&os,std::uint8_t x){return os<<(int)x;}
std::ostream&operator<<(std::ostream&os,const __int128_t &u){if(!u)os<<"0";__int128_t tmp=u<0?(os<<"-",-u):u;std::string s;while(tmp)s+='0'+(tmp%10),tmp/=10;return std::reverse(s.begin(),s.end()),os<<s;}
std::ostream&operator<<(std::ostream&os,const __uint128_t &u){if(!u)os<<"0";__uint128_t tmp=u;std::string s;while(tmp)s+='0'+(tmp%10),tmp/=10;return std::reverse(s.begin(),s.end()),os<<s;}
#define checkpoint() (void(0))
#define debug(...) (void(0))
#define debugArray(x,n) (void(0))
#define debugMatrix(x,h,w) (void(0))
// clang-format on
template <class T, size_t B= 700> class SortedPerBucket {
 static constexpr T INF= std::numeric_limits<T>::max() / 2;
 struct Dat {
  const size_t n;
  T a[B], sorted[B], acc[B + 1];
  T add, lb, ub;
  Dat(size_t b): n(b), a{0}, sorted{0}, acc{0}, add(0), lb(-INF), ub(INF) {}
  Dat(const T *bg, size_t b): n(b), a{0}, acc{0}, add(0), lb(-INF), ub(INF) {
   for (int i= n; i--;) a[i]= *(bg + i);
   build();
  }
  inline bool eval() {
   if (add == 0 && lb == -INF && ub == INF) return false;
   for (auto &x: a) x= std::clamp(x, lb, ub) + add;
   return add= 0, lb= -INF, ub= INF, true;
  }
  inline void build() { std::copy_n(a, B, sorted), std::sort(sorted, sorted + n), std::partial_sum(sorted, sorted + n, acc + 1); }
  inline size_t idx(T x) const { return std::lower_bound(sorted, sorted + n, x) - sorted; }
  inline size_t count(T x) const { return x-= add, (x <= lb ? 0 : ub < x ? n : idx(x)); }
  inline T sum() const {
   size_t l= idx(lb), u= idx(ub);
   return acc[u] - acc[l] + lb * l + ub * (n - u) + add * n;
  }
  inline T sum(T x) const {
   if (x-= add; x <= lb) return 0;
   if (ub < x) return sum();
   size_t l= idx(lb), u= idx(x);
   return acc[u] - acc[l] + lb * l + add * u;
  }
  inline T get(size_t k) const { return std::clamp(a[k], lb, ub) + add; }
 };
 const size_t n;
 std::vector<Dat> dat;
 template <class U, class All, class One> inline U fold(size_t l, size_t r, const All &all, const One &one) const {
  U ret= 0;
  if (size_t i= l / B, j= r / B, k= l % B, m= r % B; i < j) {
   if (k) {
    for (; k < dat[i].n; ++k) ret+= one(dat[i].get(k));
    ++i;
   }
   for (; i < j; ++i) ret+= all(dat[i]);
   for (; m--;) ret+= one(dat[j].get(m));
  } else
   for (; k < m; ++k) ret+= one(dat[i].get(k));
  return ret;
 }
 template <class All, class One> inline void update(size_t l, size_t r, const All &all, const One &one) {
  if (size_t i= l / B, j= r / B, k= l % B, m= r % B; i < j) {
   if (k) {
    for (dat[i].eval(); k < dat[i].n; k++) one(dat[i].a[k]);
    dat[i].build(), ++i;
   }
   for (; i < j; ++i) all(dat[i]);
   if (m) {
    for (dat[j].eval(); m--;) one(dat[j].a[m]);
    dat[j].build();
   }
  } else {
   for (dat[i].eval(); k < m; ++k) one(dat[i].a[k]);
   dat[i].build();
  }
 }
public:
 SortedPerBucket(size_t n): n(n) {
  for (size_t l= 0, r; l < n; l= r) r= std::min(l + B, n), dat.emplace_back(r - l);
 }
 SortedPerBucket(const std::vector<T> &a): n(a.size()) {
  for (size_t l= 0, r; l < n; l= r) r= std::min(l + B, n), dat.emplace_back(a.data() + l, r - l);
 }
 // count i s.t. (l <= i < r) && (a[i] < ub)
 size_t count(size_t l, size_t r, T ub) const {
  return fold<size_t>(l, r, [&](const Dat &d) { return d.count(ub); }, [&](T x) { return x < ub; });
 }
 // count i s.t. (l <= i < r) && (lb <= a[i] < ub)
 size_t count(size_t l, size_t r, T lb, T ub) const { return count(l, r, ub) - count(l, r, lb); }
 // sum a[i] s.t. (l <= i < r)
 T sum(size_t l, size_t r) const {
  return fold<T>(l, r, [&](const Dat &d) { return d.sum(); }, [&](T x) { return x; });
 }
 // sum a[i] s.t. (l <= i < r) && (a[i] < ub)
 T sum(size_t l, size_t r, T ub) const {
  return fold<T>(l, r, [&](const Dat &d) { return d.sum(ub); }, [&](T x) { return x < ub ? x : 0; });
 }
 // sum a[i] s.t. (l <= i < r)  && (lb <= a[i] < ub)
 T sum(size_t l, size_t r, T lb, T ub) const { return sum(l, r, ub) - sum(l, r, lb); }
 void set(size_t k, T x) {
  size_t i= k / B, j= k % B;
  dat[i].eval(), dat[i].a[j]= x, dat[i].build();
 }
 T get(size_t k) const { return dat[k / B].get(k % B); }
 T operator[](size_t k) const { return get(k); }
 void add(size_t l, size_t r, T v) {
  update(l, r, [&](Dat &d) { d.add+= v; }, [&](T &x) { x+= v; });
 }
 void chmin(size_t l, size_t r, T ub) {
  auto f= [&](Dat &d) {
   T b= ub - d.add;
   d.ub= std::min(d.ub, b), d.lb= std::min(d.lb, b);
  };
  update(l, r, f, [&](T &x) { x= std::min(x, ub); });
 }
 void chmax(size_t l, size_t r, T lb) {
  auto f= [&](Dat &d) {
   T a= lb - d.add;
   d.lb= std::max(d.lb, a), d.ub= std::max(d.ub, a);
  };
  update(l, r, f, [&](T &x) { x= std::max(x, lb); });
 }
 void chclamp(size_t l, size_t r, T lb, T ub) {
  auto f= [&](Dat &d) {
   T a= lb - d.add, b= ub - d.add;
   d.ub= std::clamp(d.ub, a, b), d.lb= std::clamp(d.lb, a, b);
  };
  update(l, r, f, [&](T &x) { x= std::clamp(x, lb, ub); });
 }
};
using namespace std;
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 int N;
 cin >> N;
 vector<int> A(N + 1);
 for (int i= 0; i <= N; ++i) cin >> A[i];
 vector<vector<int>> tree(N + 1);
 for (int i= 0; i < N; ++i) {
  int u, v;
  cin >> u >> v;
  tree[u].push_back(v);
  tree[v].push_back(u);
 }
 constexpr long long INF= 1e10;
 SortedPerBucket<long long, 700> sqrtdc(N + 1);
 int cnt= 0;
 auto sum= [&]() {
  long long l= 0, h= 1e9 + 10;
  size_t m= cnt / 2;
  while (h - l > 1) {
   long long x= (l + h) / 2;
   (sqrtdc.count(0, N + 1, x, INF) <= m ? h : l)= x;
  }
  debug(cnt, l);
  debug(sqrtdc.sum(0, N + 1));
  debug(sqrtdc.sum(0, N + 1, l, INF));
  long long ret= sqrtdc.sum(0, N + 1, l, INF) * 2 - sqrtdc.sum(0, N + 1);
  debug(ret);
  debug(sqrtdc.count(0, N + 1, l, INF));
  ret+= l * (cnt - 2 * sqrtdc.count(0, N + 1, l, INF));
  debug(ret);
  return ret;
 };
 vector<int> mn(N + 1), mx(N + 1);
 vector<long long> ans(N + 1);
 auto dfs= [&](auto &&dfs, int v, int p, int d) -> void {
  debug(v, p, d);
  if (d < 2) {
   ans[v]= -1;
  } else if (mn[v] == mx[v]) {
   ans[v]= 1;
  } else {
   ++cnt;
   sqrtdc.set(0, mn[v]);
   ans[v]= sum();
   sqrtdc.set(0, mx[v]);
   ans[v]= min(ans[v], sum());
   sqrtdc.set(0, 0);
   --cnt;
  }
  for (int u: tree[v]) {
   if (u == p) continue;
   mn[u]= mn[v], mx[u]= mx[v];
   if (A[u] < mn[u]) swap(mn[u], A[u]);
   else if (mx[u] < A[u]) swap(mx[u], A[u]);
   sqrtdc.set(u, A[u]);
   ++cnt;
   dfs(dfs, u, v, d + 1);
   sqrtdc.set(u, 0);
   --cnt;
  }
 };
 for (int u: tree[0]) {
  tie(mn[u], mx[u])= minmax(A[0], A[u]);
  dfs(dfs, u, 0, 1);
 }
 for (int i= 1; i <= N; ++i) cout << ans[i] << "\n";
 return 0;
}
0