結果
問題 | No.763 Noelちゃんと木遊び |
ユーザー |
|
提出日時 | 2019-03-23 20:32:51 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 89 ms / 2,000 ms |
コード長 | 1,069 bytes |
コンパイル時間 | 864 ms |
コンパイル使用メモリ | 84,304 KB |
実行使用メモリ | 20,504 KB |
最終ジャッジ日時 | 2024-09-24 17:53:41 |
合計ジャッジ時間 | 2,911 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 21 |
ソースコード
#include <string>#include <utility>#include <algorithm>#include <map>#include <set>#include <vector>#include <cmath>#include <cstdlib>#include <queue>#include <stack>#include <iomanip>#include <iostream>using namespace std;#define REP(i, n) for(int i = 0;i < n;i++)#define REPR(i, n) for(int i = n;i >= 0;i--)#define FOR(i, m, n) for(ll i = m;i < n;i++)#define FORR(i, m, n) for(ll i = m;i >= n;i--)#define REPO(i, n) for(int i = 1;i <= n;i++)#define ll long long#define INF 1999999999#define MINF -1999999999#define INF64 1999999999999999999#define ALL(n) n.begin(),n.end()#define MOD 1000000007ll n, dp[110000][2];vector<ll> e[200000];void dfs(ll a, ll b) {REP(i, e[a].size()) {if (e[a][i] != b) {dfs(e[a][i], a);dp[a][0] += max(dp[e[a][i]][0], dp[e[a][i]][1]);dp[a][1] += max(dp[e[a][i]][0], dp[e[a][i]][1] - 1);}}dp[a][1]++;}int main() {cin >> n;REP(i, n - 1) {ll a, b;cin >> a >> b;a--; b--;e[a].push_back(b);e[b].push_back(a);}dfs(0, 0);cout << max(dp[0][0], dp[0][1]) << endl;}