結果
問題 | No.763 Noelちゃんと木遊び |
ユーザー |
![]() |
提出日時 | 2019-11-06 02:50:21 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 88 ms / 2,000 ms |
コード長 | 1,792 bytes |
コンパイル時間 | 1,918 ms |
コンパイル使用メモリ | 174,096 KB |
実行使用メモリ | 14,136 KB |
最終ジャッジ日時 | 2024-09-15 00:17:38 |
合計ジャッジ時間 | 4,865 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 21 |
ソースコード
//#define _GLIBCXX_DEBUG#include "bits/stdc++.h"using namespace std;//------------------------------- Libraries --------------------------------////------------------------------- Type Names -------------------------------//using i64 = int_fast64_t;using seika = string;//akari : 1D, yukari : 2D, maki : 3D vectortemplate <class kizuna>using akari = vector<kizuna>;template <class yuzuki>using yukari = akari<akari<yuzuki>>;template <class tsurumaki>using maki = akari<yukari<tsurumaki>>;//akane : ascending order, aoi : decending ordertemplate <class kotonoha>using akane = priority_queue<kotonoha, akari<kotonoha>, greater<kotonoha>>;template <class kotonoha>using aoi = priority_queue<kotonoha>;//------------------------------- Dubug Functions ---------------------------//inline void print(){cout << endl;}template <typename First, typename... Rest>void print(const First &first, const Rest &... rest){cout << first << ' ';print(rest...);}//------------------------------- Solver ------------------------------------//void solve(){int n;cin >> n;yukari<int> g(n);for (int i = 0; i < n - 1; i++){int u, v;cin >> u >> v;u--, v--;g[u].push_back(v);g[v].push_back(u);}yukari<int> dp(2, akari<int>(n));auto dfs = [&](auto &&dfs, int v = 0, int p = -1) -> void {dp[0][v] = 1;for (int nv : g[v]){if (nv == p){continue;}dfs(dfs, nv, v);dp[1][v] += max(dp[1][nv], dp[0][nv]);dp[0][v] += max(dp[1][nv], dp[0][nv] - 1);}};dfs(dfs);cout << max(dp[0][0], dp[1][0]) << endl;}int main(){solve();return 0;}