結果
問題 | No.763 Noelちゃんと木遊び |
ユーザー |
![]() |
提出日時 | 2019-02-27 11:37:44 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 78 ms / 2,000 ms |
コード長 | 1,316 bytes |
コンパイル時間 | 1,316 ms |
コンパイル使用メモリ | 161,852 KB |
実行使用メモリ | 18,376 KB |
最終ジャッジ日時 | 2024-06-23 05:03:10 |
合計ジャッジ時間 | 3,540 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 21 |
ソースコード
#include <bits/stdc++.h>using namespace std;#ifdef LOCAL#define eprintf(...) fprintf(stderr, __VA_ARGS__)#else#define eprintf(...) 42#endif#define rep(i,n) for(int i=0;i<(int)(n);i++)#define repi(i,a,b) for(int i=(int)(a);i<(int)(b);i++)#define all(x) (x).begin(),(x).end()#define foreach(u,v) for(auto (u) : (v))#define pb push_back#define mp make_pair#define mt make_tupletypedef long long ll;typedef pair<int, int> pii;typedef vector<int> vi;typedef vector<vi> vvi;typedef pair<ll, ll> pll;typedef vector<ll> vl;const int inf = 1e9;const ll linf = 1LL<<60;const ll mod = 1e9 + 7;const double eps = 1e-9;/*{dp[i][j]iを根とする部分木でj=0 iを削除しないj=1 iを削除するときの連結成分の個数}*/vector<int> g[100000];ll dp[100001][2];void dfs(int x, int par = -1){dp[x][0] = 1;dp[x][1] = 0;for(auto to : g[x]){if(to == par) continue;dfs(to, x);dp[x][0] += dp[to][1];dp[x][1] += max(dp[to][0], dp[to][1]);}// cout << x << " : " << dp[x][0] << " , " << dp[x][1] << endl;}int main(){int n;cin >> n;rep(i, n-1){int x, y;cin >> x >> y;x--; y--;g[x].pb(y);g[y].pb(x);}dfs(0);ll ans = max(dp[0][0], dp[0][1]);cout << ans << endl;return 0;}