제출 #835813

#제출 시각아이디문제언어결과실행 시간메모리
835813elkernosChase (CEOI17_chase)C++17
100 / 100
332 ms265000 KiB
// clang-format off #include <bits/stdc++.h> // #include <ext/pb_ds/assoc_container.hpp> // #include <ext/pb_ds/tree_policy.hpp> using namespace std; // using namespace __gnu_pbds; // template <typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; #define sim template < class c #define ris return * this #define dor > debug & operator << #define eni(x) sim > typename enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) { sim > struct rge { c b, e; }; sim > rge<c> range(c i, c j) { return rge<c>{i, j}; } sim > auto dud(c* x) -> decltype(cerr << *x, 0); sim > char dud(...); struct debug { #ifdef XOX ~debug() { cerr << endl; } eni(!=) cerr << boolalpha << i; ris; } eni(==) ris << range(begin(i), end(i)); } sim, class b dor(pair < b, c > d) { ris << "(" << d.first << ", " << d.second << ")"; } sim dor(rge<c> d) { *this << "["; for (auto it = d.b; it != d.e; ++it) *this << ", " + 2 * (it == d.b) << *it; ris << "]"; } #else sim dor(const c&) { ris; } #endif }; #define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] " struct { template <class T> operator T() { T x; cin >> x; return x; } } in; #define endl '\n' #define pb emplace_back #define vt vector #define all(x) begin(x), end(x) #define sz(x) (int)(x).size() using i64 = long long; // #define int long long // clang-format on template<typename T> void ckmax(T& a, T b) { a = max(a, b); } int32_t main() { int n = in, v = in; vector<int> c(n + 1); for(int i = 1; i <= n; i++) c[i] = in; vector<vector<int>> g(n + 1); vector<i64> ile(n + 1); for(int i = 1; i < n; i++) { int a = in, b = in; g[a].emplace_back(b), g[b].emplace_back(a); ile[a] += c[b]; ile[b] += c[a]; } i64 ans = 0; vector<vector<i64>> dpup(n + 1, vector<i64>(v + 1)), dpdown(n + 1, vector<i64>(v + 1)); function<void(int, int)> dfs = [&](int u, int p) { dpup[u][1] = ile[u]; vector<i64> przepisz_up(v + 1), przepisz_down(v + 1); for(int to : g[u]) { if(to == p) continue; dfs(to, u); for(int j = 1; j <= v; j++) { i64 dist_up = max(dpup[to][j], dpup[to][j - 1] + ile[u] - c[to]); i64 dist_down = max(dpdown[to][j], dpdown[to][j - 1] + ile[to] - c[u]); przepisz_up[j] = dist_up; przepisz_down[j] = dist_down; if(j != v) { ckmax(ans, dpup[u][v - j] + dist_down); ckmax(ans, dpdown[u][v - j] + dist_up); ckmax(ans, dpdown[to][j] + ile[u]); } } for(int j = 1; j <= v; j++) { ckmax(dpup[u][j], przepisz_up[j]); ckmax(dpdown[u][j], przepisz_down[j]); ckmax(ans, dpup[u][j]); } } }; if(v == 0) { cout << 0; exit(0); } dfs(1, 0); cout << ans << endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...