結果

問題 No.1221 木 *= 3
ユーザー HaarHaar
提出日時 2020-09-04 23:06:45
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 118 ms / 2,000 ms
コード長 4,613 bytes
コンパイル時間 2,324 ms
コンパイル使用メモリ 212,668 KB
実行使用メモリ 22,340 KB
最終ジャッジ日時 2023-08-17 20:40:18
合計ジャッジ時間 6,009 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,376 KB
testcase_01 AC 2 ms
4,376 KB
testcase_02 AC 2 ms
4,380 KB
testcase_03 AC 2 ms
4,376 KB
testcase_04 AC 2 ms
4,376 KB
testcase_05 AC 1 ms
4,380 KB
testcase_06 AC 2 ms
4,376 KB
testcase_07 AC 103 ms
22,336 KB
testcase_08 AC 102 ms
22,072 KB
testcase_09 AC 103 ms
22,268 KB
testcase_10 AC 100 ms
22,340 KB
testcase_11 AC 104 ms
22,328 KB
testcase_12 AC 87 ms
17,128 KB
testcase_13 AC 85 ms
16,980 KB
testcase_14 AC 88 ms
17,120 KB
testcase_15 AC 88 ms
17,060 KB
testcase_16 AC 87 ms
17,120 KB
testcase_17 AC 118 ms
17,464 KB
testcase_18 AC 113 ms
17,616 KB
testcase_19 AC 116 ms
17,512 KB
testcase_20 AC 115 ms
17,508 KB
testcase_21 AC 116 ms
17,524 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

#ifdef DEBUG
#include <Mylib/Debug/debug.cpp>
#else
#define dump(...) ((void)0)
#endif

template <typename T, typename U>
bool chmin(T &a, const U &b){
  return (a > b ? a = b, true : false);
}

template <typename T, typename U>
bool chmax(T &a, const U &b){
  return (a < b ? a = b, true : false);
}

template <typename T, size_t N, typename U>
void fill_array(T (&a)[N], const U &v){
  std::fill((U*)a, (U*)(a + N), v);
}

template <typename T, size_t N, size_t I = N>
auto make_vector(const std::array<int, N> &a, T value = T()){
  static_assert(I >= 1);
  static_assert(N >= 1);
  if constexpr (I == 1){
    return std::vector<T>(a[N - I], value);
  }else{
    return std::vector(a[N - I], make_vector<T, N, I - 1>(a, value));
  }
}

template <typename T>
std::ostream& operator<<(std::ostream &s, const std::vector<T> &a){
  for(auto it = a.begin(); it != a.end(); ++it){
    if(it != a.begin()) s << " ";
    s << *it;
  }
  return s;
}

template <typename T>
std::istream& operator>>(std::istream &s, std::vector<T> &a){
  for(auto &x : a) s >> x;
  return s;
}

/**
 * @title Basic graph
 * @docs graph.md
 */
template <typename T>
struct Edge {
  int from, to;
  T cost;
  int index = -1;
  Edge(){}
  Edge(int from, int to, T cost): from(from), to(to), cost(cost){}
  Edge(int from, int to, T cost, int index): from(from), to(to), cost(cost), index(index){}
};

template <typename T>
struct Graph {
  using weight_type = T;
  using edge_type = Edge<T>;

  std::vector<std::vector<Edge<T>>> data;

  auto& operator[](size_t i){return data[i];}
  const auto& operator[](size_t i) const {return data[i];}

  auto begin() const {return data.begin();}
  auto end() const {return data.end();}

  Graph(){}
  Graph(int N): data(N){}

  bool empty() const {return data.empty();}
  int size() const {return data.size();}

  void add_edge(int i, int j, T w, int index = -1){
    data[i].emplace_back(i, j, w, index);
  }

  void add_undirected(int i, int j, T w, int index = -1){
    add_edge(i, j, w, index);
    add_edge(j, i, w, index);
  }

  template <size_t I, bool DIRECTED = true, bool WEIGHTED = true>
  void read(int M){
    for(int i = 0; i < M; ++i){
      int u, v; std::cin >> u >> v;
      u -= I;
      v -= I;
      T w = 1;
      if(WEIGHTED) std::cin >> w;
      if(DIRECTED) add_edge(u, v, w, i);
      else add_undirected(u, v, w, i);
    }
  }
};

template <typename T>
using Tree = Graph<T>;

/**
 * @title Rooting
 * @docs rooting.md
 */
template <typename T>
void rooting(Tree<T> &tree, int cur, int par = -1){
  if(par != -1){
    for(auto it = tree[cur].begin(); it != tree[cur].end(); ++it){
      if(it->to == par){
        tree[cur].erase(it);
        break;
      }
    }
  }

  for(auto &e : tree[cur]){
    rooting(tree, e.to, cur);
  }
}


/**
 * @title Fixed point combinator
 * @docs fix_point.md
 */
template <typename F>
struct FixPoint : F {
  explicit constexpr FixPoint(F &&f) noexcept : F(std::forward<F>(f)){}

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

template <typename F>
inline constexpr auto make_fix_point(F &&f){
  return FixPoint<F>(std::forward<F>(f));
}

template <typename F>
inline constexpr auto make_fix_point(F &f){
  return FixPoint<F>(std::forward<F>(f));
}


namespace solver{
  void init(){
    std::cin.tie(0);
    std::ios::sync_with_stdio(false);
    std::cout << std::fixed << std::setprecision(12);
    std::cerr << std::fixed << std::setprecision(12);
    std::cin.exceptions(std::ios_base::failbit);
  }

  constexpr int64_t INF = 1LL << 50;

  void solve(){
    int N; std::cin >> N;
    std::vector<int64_t> a(N), b(N); std::cin >> a >> b;

    Tree<int> tree(N);
    tree.read<1, false, false>(N - 1);
    rooting(tree, 0);

    auto dp = make_vector<int64_t, 2>({N, 2}, -INF);

    auto rec =
      make_fix_point(
        [&](auto &&rec, int cur) -> void {
          for(auto &e : tree[cur]){
            rec(e.to);
          }

          dp[cur][0] = a[cur];
          for(auto &e : tree[cur]){
            dp[cur][0] += std::max(dp[e.to][0], dp[e.to][1]);
          }

          dp[cur][1] = 0;
          for(auto &e : tree[cur]){
            dp[cur][1] += std::max(dp[e.to][0], dp[e.to][1] + b[cur] + b[e.to]);
          }
        }
      );

    rec(0);

    int64_t ans = std::max(dp[0][0], dp[0][1]);
    std::cout << ans << "\n";
  }
}

int main(){
  solver::init();
  while(true){
    try{
      solver::solve();
    }catch(const std::istream::failure &e){
      break;
    }
  }
  return 0;
}
0