結果

問題 No.1221 木 *= 3
ユーザー Haar
提出日時 2020-09-04 23:06:45
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 151 ms / 2,000 ms
コード長 4,613 bytes
コンパイル時間 2,466 ms
コンパイル使用メモリ 206,784 KB
最終ジャッジ日時 2025-01-14 06:22:45
ジャッジサーバーID
(参考情報)
judge1 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 4
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0