結果

問題 No.899 γatheree
ユーザー ngtkanangtkana
提出日時 2019-10-05 01:28:16
言語 C++17
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 836 ms / 2,000 ms
コード長 12,245 bytes
コンパイル時間 2,767 ms
コンパイル使用メモリ 219,004 KB
実行使用メモリ 19,328 KB
最終ジャッジ日時 2024-04-14 23:25:01
合計ジャッジ時間 19,357 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 2 ms
6,944 KB
testcase_02 AC 2 ms
6,940 KB
testcase_03 AC 2 ms
6,940 KB
testcase_04 AC 3 ms
6,940 KB
testcase_05 AC 2 ms
6,940 KB
testcase_06 AC 834 ms
18,944 KB
testcase_07 AC 828 ms
18,932 KB
testcase_08 AC 817 ms
19,072 KB
testcase_09 AC 830 ms
18,940 KB
testcase_10 AC 826 ms
19,072 KB
testcase_11 AC 836 ms
19,200 KB
testcase_12 AC 826 ms
19,072 KB
testcase_13 AC 809 ms
19,072 KB
testcase_14 AC 818 ms
19,072 KB
testcase_15 AC 828 ms
19,004 KB
testcase_16 AC 819 ms
18,944 KB
testcase_17 AC 824 ms
19,048 KB
testcase_18 AC 818 ms
19,052 KB
testcase_19 AC 821 ms
18,944 KB
testcase_20 AC 827 ms
19,072 KB
testcase_21 AC 812 ms
19,328 KB
testcase_22 AC 806 ms
19,200 KB
testcase_23 AC 807 ms
19,328 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define loop(n) for (int ngtkana_is_genius = 0; ngtkana_is_genius < int(n); ngtkana_is_genius++)
#define rep(i, begin, end) for(int i = int(begin); i < int(end); i++)
#define all(v) v.begin(), v.end()
#define rand(l, r) std::uniform_int_distribution<>(l, r)(mt)
using lint = long long;
auto cmn = [](auto& a, auto b){if (a > b) {a = b; return true;} return false;};
auto cmx = [](auto& a, auto b){if (a < b) {a = b; return true;} return false;};
void debug_impl() { std::cerr << std::endl; }
template <typename Head, typename... Tail>
void debug_impl(Head head, Tail... tail){
  std::cerr << " " << head;
  debug_impl(tail...);
}
#ifndef STOPIT
#define debug(...)\
  std::cerr << std::boolalpha << "[" << #__VA_ARGS__ << "]:";\
  debug_impl(__VA_ARGS__);\
  std::cerr << std::noboolalpha;
#else
#define debug 0;
#endif

template <typename T>
auto make_vector_impl(size_t sz, T t) {return std::vector<T>(sz, t);}

template <size_t N, typename T, typename U, std::enable_if_t<N == 1, std::nullptr_t> = nullptr>
auto make_vector(size_t sz, U u) {return make_vector_impl(sz, T(u));}

template <size_t N, typename T, std::enable_if_t<N == 1, std::nullptr_t> = nullptr>
auto make_vector(size_t sz) {return std::vector<T>(sz);}

template <size_t N, typename T, typename... Args, std::enable_if_t<N != 1, std::nullptr_t> = nullptr>
auto make_vector(size_t a, Args... args) {return make_vector_impl(a, make_vector<N - 1, T>(args...));}

template <typename T, typename Size_t>
auto& at(T& t, Size_t i) {return t.at(i);}

template <typename T, typename Size_t, typename... Args>
auto& at(T& t, Size_t i, Args... args) {return at(t.at(i), args...);}

template < typename Container, typename Value = typename Container::value_type, std::enable_if_t<!std::is_same< Container, std::string >::value, std::nullptr_t> = nullptr>
std::istream& operator>> (std::istream& is, Container& v)
  { for (auto & x : v) { is >> x; } return is; }

template < typename Container, typename Value = typename Container::value_type, std::enable_if_t<!std::is_same< Container, std::string >::value, std::nullptr_t> = nullptr >
std::ostream& operator<< (std::ostream& os, Container const& v) {
 os << "{";
  for (auto it = v.begin(); it != v.end(); it++)
    {os << (it != v.begin() ? "," : "") << *it;}
  return os << "}";
}

template < template < typename ... > class Tuple,  typename... Args, std::size_t ... Inds, std::size_t = std::tuple_size< Tuple < Args ... > >::value >
std::istream& tuple_input_impl(std::istream& os, Tuple<Args...>& tuple, std::integer_sequence<std::size_t, Inds...>)
  { (void)std::initializer_list<int>{((void)(os >> std::get< Inds >(tuple)), 0)...}; return os; }
template < template < typename ... > class Tuple,  typename... Args, std::size_t = std::tuple_size< Tuple < Args ... > >::value >
std::istream& operator>> (std::istream& os, Tuple<Args...>& tuple)
  { return tuple_input_impl(os, tuple, std::index_sequence_for<Args...>()); }

template < template < typename ... > class Tuple,  typename... Args, std::size_t ... Inds, std::size_t = std::tuple_size< Tuple < Args ... > >::value >
std::ostream& tuple_output_impl(std::ostream& os, const Tuple<Args...>& tuple, std::integer_sequence<std::size_t, Inds...>)
  { os << "("; (void)std::initializer_list<int>{((void)(os << (Inds > 0 ? "," : "") << std::get< Inds >(tuple)), 0)...}; return os << ")"; }
template < template < typename ... > class Tuple,  typename... Args, std::size_t = std::tuple_size< Tuple < Args ... > >::value >
std::ostream& operator<< (std::ostream& os, const Tuple<Args...>& tuple)
 { return tuple_output_impl(os, tuple, std::index_sequence_for<Args...>()); }

template< typename F >
class fixed_point : F {
  public:
    explicit constexpr fixed_point (F&& f) noexcept
      : F(std::forward< F >(f)) {}
    template< typename ... Args >
    constexpr decltype(auto) operator()(Args&& ... args) const
      { return F::operator()(*this, std::forward< Args >(args)...); }
};
template< typename F >
static inline constexpr decltype(auto) fix (F&& f) noexcept
  { return fixed_point< F >{std::forward< F >(f)}; }

template<
  typename Value1,    typename Value2,
  typename BinaryOp1, typename BinaryOp2, typename BinaryOp3,
  typename UnaryOp1,  typename UnaryOp2
  >
class lazy_segment_tree {
    struct node {
      int id, l, r;
      node(int id, int l, int r): id(id), l(l), r(r) {};
      auto size() const { return r - l; }
      auto left_child () const { assert(size() > 1); return node(id * 2,     l, (l + r) / 2); }
      auto right_child() const { assert(size() > 1); return node(id * 2 + 1, (l + r) / 2, r); }
    };

    int                   size;
    int                   n;
    int                   N;
    BinaryOp1             op1;
    BinaryOp2             op2;
    BinaryOp3             op3;
    Value1                id1;
    Value2                id2;
    UnaryOp1              expand;
    UnaryOp2              shrink;
    std::vector< Value1 > table;
    std::vector< Value2 > lazy;
    node                  initial_node;

    auto& op1_eq(Value1& x, Value1 y) {return x = op1(x, y);}
    auto& op2_eq(Value1& x, Value2 y) {return x = op2(x, y);}
    auto& op3_eq(Value2& x, Value2 y) {return x = op3(x, y);}

    void cal(int u)
      { table.at(u) = op1(table.at(2 * u), table.at(2 * u + 1)); }

    auto chain(int u) const {
      auto ret = std::vector<int>{};
      for (auto i = u; i > 0; i /= 2)
        { ret.emplace_back(i); }
      std::reverse(ret.begin(), ret.end());
      return ret;
    }

    auto prop(int u) {
      op2_eq(table.at(u), lazy.at(u));
      if (u < n) {
        op3_eq(lazy.at(2 * u),     shrink(lazy.at(u)));
        op3_eq(lazy.at(2 * u + 1), shrink(lazy.at(u)));
      }
      lazy.at(u)     = id2;
      return table.at(u);
    }

    auto query_base(int l, int r, Value2 val, const node& now) {
      prop(now.id);
      if (now.r <= l || r <= now.l) return id1;
      else if (l <= now.l && now.r <= r) {
        op3_eq(lazy.at(now.id), val);
        return prop(now.id);
      }
      else {
        auto ret =op1(
          query_base(l, r, shrink(val), now.left_child()),
          query_base(l, r, shrink(val), now.right_child())
        );
        cal(now.id);
        return ret;
      }
    }

  public:
    lazy_segment_tree(
      int        size,
      BinaryOp1  op1,
      BinaryOp2  op2,
      BinaryOp3  op3,
      Value1     id1,
      Value2     id2,
      UnaryOp1   expand,
      UnaryOp2   shrink
    ):
      size         (size),
      n            (std::pow(2, int(std::log2(size)) + 1)),
      N            (n * 2),
      op1          (op1),
      op2          (op2),
      op3          (op3),
      id1          (id1),
      id2          (id2),
      expand       (expand),
      shrink       (shrink),
      table        (N, id1),
      lazy         (N, id2),
      initial_node(1, 0, n)
      {
        std::mt19937 mt(std::random_device{}());
        std::uniform_int_distribution< int > dist(-1'000'000, 1'000'000);
        for (auto i = 0; i < 20; i++) {
          Value1 ex1 = dist(mt), ex1_ = dist(mt);
          Value2 ex2 = dist(mt);
          assert(op1(ex1, id1)       == ex1);
          assert(op2(ex1, id2)       == ex1);
          assert(op3(ex2, id2)       == ex2);
          assert(shrink(expand(ex2)) == ex2);
          assert(op2(op1(ex1, ex1_), expand(ex2)) == op1(op2(ex1, ex2), op2(ex1_, ex2)));
        }
      }

    void build(const Value1 x)
      { std::fill(table.begin(), table.end(), x); }

    void build(const std::vector< Value1 >& v) {
      assert(int(v.size()) <= n);
      std::copy(v.begin(), v.end(), table.begin() + n);
      for (int i = n - 1; i >= 0; i--)
        { cal(i); }
    }

    void act(int l, int r, Value2 val) {
      for (int i = 1; i < n; i *= 2)
        { val = expand(val); }
      query_base(l, r, val, initial_node);
    }

    auto query(int l, int r)
      { return query_base(l, r, id2, initial_node); }

    auto quiet_at(int i) const {
      i += n;
      auto actor = id2;
      for (auto j : chain(i)) {
        actor = shrink(actor);
        actor = op3(actor, lazy.at(j));
      }
      return op2(table.at(i), actor);
    }

    auto quiet_collect() const {
      auto ret = std::vector< Value1 >(size);
      for (auto i = 0; i < size; i++)
        { ret.at(i) = quiet_at(i); }
      return ret;
    }

    auto at(int i) {
      i += n;
      for (auto j : chain(i))
        { prop(j); }
      return table.at(i);
    }

    auto collect() {
      for (int i = 0; i < N; i++)
        { prop(i); }
      auto ret = std::vector< Value1 >(size);
      for (auto i = 0; i < size; i++)
        { ret.at(i) = table.at(i + n); }
      return ret;
    }
};

template< class Value1, class Value2, class BinaryOp1, class BinaryOp2, class BinaryOp3, class UnaryOp1, class UnaryOp2 >
auto make_lazy_segment_tree(
  int        size,
  BinaryOp1  op1,
  BinaryOp2  op2,
  BinaryOp3  op3,
  Value1     id1,
  Value2     id2,
  UnaryOp1   expand,
  UnaryOp2   shrink
) {
  return lazy_segment_tree<Value1, Value2, BinaryOp1, BinaryOp2, BinaryOp3, UnaryOp1, UnaryOp2 >(
    size, op1, op2, op3, id1, id2, std::move(expand), std::move(shrink));
}

template< class Value1, class Value2, class BinaryOp1, class BinaryOp2, class BinaryOp3 >
auto make_lazy_segment_tree(
  int        size,
  BinaryOp1  op1,
  BinaryOp2  op2,
  BinaryOp3  op3,
  Value1     id1,
  Value2     id2
) {
  auto f = [](auto x){return x;};
  return make_lazy_segment_tree(size, op1, op2, op3, id1, id2, f, f);
}

template < class Value >
struct vending_machine {
  Value i;
  vending_machine(Value i) : i(i) {}
  auto issue() { return i++; }
};

int main() {
  std::cin.tie(0); std::cin.sync_with_stdio(false);
  int n; std::cin >> n;
  auto graph = make_vector< 2, int >(n, 0);
  loop(n - 1) {
    int u, v; std::cin >> u >> v;
    graph.at(u).emplace_back(v);
    graph.at(v).emplace_back(u);
  }

  // vid
  auto root = 0;
  std::vector< int > vid(n, -1);
  auto vm = vending_machine< int >(0);
  std::queue< int > que;
  que.emplace(root);
  while (!que.empty()) {
    auto crr = que.front(); que.pop();
    vid.at(crr) = vm.issue();
    for (auto nxt : graph.at(crr)) {
      if (vid.at(nxt) != -1) continue;
      que.emplace(nxt);
    }
  }

  // vid_graph
  auto vid_graph = make_vector< 2, int >(n, 0);
  std::vector< int > prt(n, -1);
  std::vector< std::pair< int, int > > chi(n);
  fix ([&](auto dfs, int crr) -> void {
    auto x = vid.at(crr);
    auto min = n, max = -1;
    for (auto const& nxt : graph.at(crr)) {
      auto y = vid.at(nxt);
      if (y < x) continue;
      prt.at(y) = x;
      cmn(min, y), cmx(max, y);
      dfs(nxt);
    }
    chi.at(x) = {min, max};
  })(root);
  std::vector< std::pair< int, int > > gchi(n, {n, -1});
  rep(y, 0, n) {
    int l, r; std::tie(l, r) = chi.at(y);
    auto x = prt.at(y);
    if (x != -1 && r != -1) {
      cmn(gchi.at(x).first , l);
      cmx(gchi.at(x).second, r);
    }
  }

  // inverse
  std::vector< int > ord(n);
  rep(i, 0, n)
    { ord.at(vid.at(i)) = i; }

  // segtree
  auto a = make_lazy_segment_tree(
    n,
    [](auto x, auto y){ return x + y; },
    [](auto x, auto y){ return y == -1 ? x : y; },
    [](auto x, auto y){ return y == -1 ? x : y; },
    0LL,
    -1LL,
    [](auto x){ return x == -1 ? -1 : 2 * x; },
    [](auto x){ return x == -1 ? -1 : x / 2; }
  );
  std::vector< lint > a_input(n);
  rep(i, 0, n) {
    int x; std::cin >> x;
    a_input.at(vid.at(i)) = x;
  }
  a.build(a_input);

  // queries
  int q; std::cin >> q;
  loop(q) {
    int x; std::cin >> x;
    x = vid.at(x);
    lint ret = 0;

    auto sweep = [&] (auto l, auto r) {
      r++;
      ret += a.query(l, r);
      a.act(l, r, 0LL);
    };

    auto y = prt.at(x);
    if (y != -1) {
      sweep(y, y);
      int l, r; std::tie(l, r) = chi.at(y);
      if (r != -1) {
        sweep(l, r);
      }
      auto z = prt.at(y);
      if (z != -1) {
        sweep(z, z);
      }
    } else {
      sweep(x, x);
    }

    int l, r; std::tie(l, r) = chi.at(x);
    if (r != -1) {
      sweep(l, r);
    }
    int L, R; std::tie(L, R) = gchi.at(x);
    if (R != -1) {
      sweep(L, R);
    }

    a.act(x, x + 1, ret);
    std::cout << ret << std::endl;
  }
  return 0;
}
0