#include #include struct Node { std::list neighbourList; bool marked; Node(): marked(false) { } }; int main() { unsigned n, i, a, b, cuts; scanf("%u", &n); Node nodes[n + 1]; for(i = 1; i <= n - 1; ++i) { scanf("%u %u", &a, &b); nodes[a].neighbourList.push_back(b); nodes[b].neighbourList.push_back(a); } cuts = 0; for(i = 1; i <= n; ++i) { if(nodes[i].neighbourList.size() > 2) { b = nodes[i].neighbourList.size() - 2; for(unsigned neighbour : nodes[i].neighbourList) { if(nodes[neighbour].neighbourList.size() > 2 && nodes[neighbour].marked) { --b; } } cuts += b; nodes[i].marked = true; } } printf("%u\n", cuts); return 0; }