結果
問題 | No.1221 木 *= 3 |
ユーザー |
|
提出日時 | 2020-09-05 15:41:22 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 215 ms / 2,000 ms |
コード長 | 1,639 bytes |
コンパイル時間 | 1,398 ms |
コンパイル使用メモリ | 117,880 KB |
最終ジャッジ日時 | 2025-01-14 07:11:47 |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 18 |
ソースコード
#include <cmath>#include <vector>#include <iostream>#include <algorithm>#include <set>#include <iomanip>#include <numeric>#include <queue>#include <string>#include <map>#include <fstream>#include <cassert>#include <stack>int main() {int n; std::cin >> n;std::vector<int> remove_score(n), rest_score(n);for (auto& a : remove_score) std::cin >> a;for (auto& b : rest_score) std::cin >> b;std::vector<std::vector<int>> nodes(n);for (auto i = 1; i < n; ++i) {int u, v; std::cin >> u >> v; --u; --v;nodes[u].push_back(v);nodes[v].push_back(u);}std::vector<int> parent(n, -1), node_count(n, 0);std::queue<int> queue; queue.push(0);while (!queue.empty()) {const auto front = queue.front(); queue.pop();node_count[front] = nodes[front].size();for (const auto to : nodes[front]) {if (node_count[to] == 0) {queue.push(to);parent[to] = front;}}}std::vector<long long int> remove(n), not_remove(n, 0);for (auto i = 0; i < n; ++i) {if (i > 0 && node_count[i] == 1) queue.push(i);remove[i] = remove_score[i];}while (!queue.empty()) {const auto front = queue.front(); queue.pop();for (const auto child : nodes[front]) if (parent[front] != child) {not_remove[front] += std::max(not_remove[child] + rest_score[front] + rest_score[child], remove[child]);remove[front] += std::max(not_remove[child], remove[child]);}if (parent[front] > 0 && --node_count[parent[front]] == 1) {queue.push(parent[front]);}if (parent[front] == 0 && --node_count[0] == 0) {queue.push(0);}}std::cout << std::max(remove[0], not_remove[0]) << '\n';}