fork download
  1. #include <bits/stdc++.h>
  2. #define name "BC"
  3. #define FOR(i, a, b) for (ll i = (a); i <= (b); ++i)
  4. #define FOD(i, a, b) for (ll i = (a); i >= (b); --i)
  5. #define FOO(i, n) for (int i = 0; i < (n); ++i)
  6. #define MEM(a, val) memset(a, val, sizeof(a))
  7. #define all(x) (x).begin(), (x).end()
  8. #define el '\n'
  9. #define f first
  10. #define se second
  11. #define pb push_back
  12. using namespace std;
  13. typedef long long ll;
  14. typedef pair<int, int> pi;
  15.  
  16. template<class t> bool cmi(t &a, const t &b) { return b < a && (a = b, 1); }
  17. template<class t> bool cma(t &a, const t &b) { return b > a && (a = b, 1); }
  18. const int inf = 1e9+7;
  19. const int nx = 2e5+3;
  20. int n;
  21. vector<int> ad[nx];
  22. int dp[nx];
  23. int run[nx];
  24. int tg[nx];
  25. void dfs(int z,int par) {
  26. int best = 0;
  27. int tot = 0;
  28. run[z] = inf;
  29. tg[z] = tg[par]+1;
  30. int child = 0;
  31. for (auto x:ad[z]) {
  32. if (x == par) continue;
  33. ++child;
  34. dfs(x,z);
  35. if (run[x]+1 < run[z]) {
  36. run[z] = run[x]+1;
  37. best = dp[x];
  38. }
  39. tot += dp[x];
  40. }
  41. if (tg[z] < run[z]) dp[z] = tot;
  42. else dp[z] = best;
  43. if (!child) run[z] = 0,dp[z] = 1;
  44. }
  45. int main() {
  46. if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
  47. else if (fopen(".inp", "r")) { freopen(".inp", "r", stdin); freopen(".out", "w", stdout); }
  48. ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  49. cin >> n;
  50. FOR(i,1,n-1) {
  51. int x,y; cin >> x >> y;
  52. ad[x].pb(y);
  53. ad[y].pb(x);
  54. }
  55. tg[0] = -1;
  56. dfs(1,0);
  57. cout << dp[1];
  58. // FOR(i,1,n) cout << i << ' ' << dp[i] << '\n';
  59. return 0;
  60. }
Success #stdin #stdout 0s 7360KB
stdin
Standard input is empty
stdout
1