fork download
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int MAXN = 1E5+2;
  5. int n;
  6. int ans = 0;
  7. vector<vector<int> > g;
  8. vector<int> par(MAXN, -1);
  9. vector<bool> used(MAXN, 0);
  10. vector<int> s;
  11.  
  12. void bfs(){
  13. queue<int> q; q.push(0);
  14. while(!q.empty()){
  15. int u = q.front(); q.pop();
  16. s.push_back(u);
  17. for(int v : g[u]){
  18. if(v!= par[u]){
  19. par[v] = u;
  20. q.push(v);
  21. }
  22. }
  23. }
  24. }
  25.  
  26. int main() {
  27. cin >> n; g.assign(n, vector<int>());
  28. for(int i=1; i< n; ++i){
  29. int u, v; cin >> u >> v; --u; --v;
  30. g[u].push_back(v);
  31. g[v].push_back(u);
  32. }
  33. bfs();
  34. for(int i= n-1; i>=0; --i){
  35. if(used[s[i]]) continue;
  36. if(par[s[i]]!= -1 && !used[par[s[i]]]){
  37. ++ans;
  38. used[s[i]] = used[par[s[i]]] = 1;
  39. }
  40. }
  41. cout << ans;
  42. return 0;
  43. }
Success #stdin #stdout 0s 4212KB
stdin
3 
1 2
2 3
stdout
1