tree_matching_1130.cpp (838B)
1 #include <iostream> 2 #include <vector> 3 4 int f(const std::vector<std::vector<int>>& a, 5 std::vector<std::vector<int>>& t, int v, int p, bool x) { 6 if (t[v][x] != -1) return t[v][x]; 7 if (p != -1 && a[v].size() == 1) return t[v][x] = 0; 8 9 t[v][x] = 0; 10 for (auto u : a[v]) { 11 if (u == p) continue; 12 t[v][x] += f(a, t, u, v, false); 13 } 14 if (x) return t[v][x]; 15 16 for (auto u : a[v]) { 17 if (u == p) continue; 18 if (f(a, t, u, v, true) == t[u][false]) { 19 t[v][x]++; 20 break; 21 } 22 } 23 return t[v][x]; 24 } 25 26 int main() { 27 int n, x, y; 28 std::cin >> n; 29 std::vector<std::vector<int>> a(n); 30 for (int i = 0; i < n-1; i++) { 31 std::cin >> x >> y; 32 a[x-1].push_back(y-1); 33 a[y-1].push_back(x-1); 34 } 35 if (n == 1) { 36 std::cout << "0\n"; 37 return 0; 38 } 39 std::vector<std::vector<int>> t(n, {-1, -1}); 40 std::cout << f(a, t, 0, -1, false) << "\n"; 41 }