結果
問題 | No.763 Noelちゃんと木遊び |
ユーザー |
![]() |
提出日時 | 2020-08-08 10:12:03 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 106 ms / 2,000 ms |
コード長 | 1,149 bytes |
コンパイル時間 | 2,319 ms |
コンパイル使用メモリ | 196,372 KB |
最終ジャッジ日時 | 2025-01-12 18:47:10 |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 21 |
ソースコード
#include <bits/stdc++.h>#define rep(a,n) for (ll a = 0; a < (n); ++a)using namespace std;typedef long long ll;using ll = long long;typedef pair<int,int> P;typedef pair<P,ll> PP;using Graph = vector<vector<ll> >;template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }const ll INF = 1e18;Graph g;ll n;bool ok[100010];ll dp[100010];void dfs(int v,int p=-1){int deg = g[v].size();if(p!=-1&°==1){dp[v]=1;return;}int res = 0;for(int i=0;i<deg;i++){int u = g[v][i];if(u==p)continue;dfs(u,v);if(ok[u]){res += dp[u];ok[v]=false;}else{res += dp[u];}}if(ok[v])res++;dp[v]=res;return;}int main(){cin >> n;g.resize(n);rep(i,n)ok[i]=true;rep(I,n-1){int u,v;cin >> u >> v;u--;v--;g[u].push_back(v);g[v].push_back(u);}dfs(0,-1);cout << dp[0] << endl;return 0;}