結果
問題 | No.763 Noelちゃんと木遊び |
ユーザー |
![]() |
提出日時 | 2018-12-20 19:51:31 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 100 ms / 2,000 ms |
コード長 | 786 bytes |
コンパイル時間 | 886 ms |
コンパイル使用メモリ | 73,040 KB |
実行使用メモリ | 18,432 KB |
最終ジャッジ日時 | 2024-09-25 09:10:33 |
合計ジャッジ時間 | 3,161 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 21 |
ソースコード
#include <iostream>#include <vector>using namespace std;vector<int> path[100010];bool visited[100010];pair<int, int> dfs(int v) {visited[v] = true;vector<pair<int, int>> res;for (int sv : path[v]) {if (visited[sv]) continue;res.push_back(dfs(sv));}pair<int, int> ret = make_pair(0, 1);for (auto p : res) {ret.first += max(p.first, p.second);ret.second += max(p.first, p.second - 1);}return ret;}int main() {int N;cin >> N;for (int i = 0; i < N - 1; ++i) {int u, v;cin >> u >> v;--u, --v;path[u].push_back(v);path[v].push_back(u);}pair<int, int> ret = dfs(0);cout << max(ret.first, ret.second) << endl;return 0;}