結果
問題 | No.763 Noelちゃんと木遊び |
ユーザー |
![]() |
提出日時 | 2022-09-08 03:06:46 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 97 ms / 2,000 ms |
コード長 | 815 bytes |
コンパイル時間 | 1,935 ms |
コンパイル使用メモリ | 177,336 KB |
実行使用メモリ | 17,920 KB |
最終ジャッジ日時 | 2024-11-23 19:02:18 |
合計ジャッジ時間 | 4,967 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 21 |
ソースコード
#include <bits/stdc++.h>using namespace std;#define rep(i,n) for(int i=0;i<(n);i++)using Graph = vector<vector<int>>;vector<bool> seen;vector<int> dp_del;vector<int> dp_rem;void dfs(const Graph &G, int v) {seen[v] = true;for (auto next_v : G[v]) {if (seen[next_v]) continue;dfs(G, next_v);dp_del[v] += max(dp_rem[next_v],dp_del[next_v]);dp_rem[v] += dp_del[next_v];}}int main(){int n;cin >> n;Graph g(n);vector<int> u(n-1),v(n-1);rep(i,n-1) {cin >> u[i] >> v[i];u[i]--,v[i]--;g[u[i]].push_back(v[i]);g[v[i]].push_back(u[i]);}seen.assign(n,false);dp_del.assign(n,0);dp_rem.assign(n,1);dfs(g,0);cout << max(dp_del[0],dp_rem[0]) << endl;return 0;}