結果
問題 | No.763 Noelちゃんと木遊び |
ユーザー |
|
提出日時 | 2023-02-10 13:04:43 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 85 ms / 2,000 ms |
コード長 | 1,397 bytes |
コンパイル時間 | 3,895 ms |
コンパイル使用メモリ | 255,180 KB |
最終ジャッジ日時 | 2025-02-10 11:53:15 |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 21 |
ソースコード
#include <bits/stdc++.h>#include <atcoder/all>#define rep(i, n) for (int i = 0; i < (int)(n); i++)using namespace atcoder;using ll = long long;const ll MOD1 = 1000000007LL;const ll MOD2 = 998244353LL;using namespace std;const vector<pair<int, int>> dpos4 = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};// const vector<pair<int, int>> dpos8 = {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}};template <typename T>bool chmax(T &a, const T &b) {if (a < b) {a = b; // aをbで更新return true;}return false;}template <typename T>bool chmin(T &a, const T &b) {if (a > b) {a = b; // aをbで更新return true;}return false;}int main() {int N;cin >> N;vector<vector<int>> edges(N);rep(i, N - 1){int u, v;cin >> u >> v;u--, v--;edges[u].push_back(v);edges[v].push_back(u);}vector<vector<ll>> dp(N, vector<ll>(2, 0));auto dfs = [&](auto self, int fr, int prev = -1) -> void {dp[fr][0] = 0;dp[fr][1] = 1;for(auto to: edges[fr]){if(to == prev) continue;self(self, to, fr);dp[fr][0] += max(dp[to][0], dp[to][1]);dp[fr][1] += max(dp[to][0], dp[to][1] - 1);}};dfs(dfs, 0);cout << max(dp[0][0], dp[0][1]) << endl;return 0;}