From 96254947699986c59f0dc63d69fd4b76bd3ed43e Mon Sep 17 00:00:00 2001
From: Sebastiano Tronto <sebastiano@tronto.net>
Date: Mon, 6 Jul 2026 19:08:08 +0200
Subject: Initial commit

---
 06_tree_algorithms/tree_matching_1130.cpp | 41 +++++++++++++++++++++++++++++++
 1 file changed, 41 insertions(+)
 create mode 100644 06_tree_algorithms/tree_matching_1130.cpp

(limited to '06_tree_algorithms/tree_matching_1130.cpp')

diff --git a/06_tree_algorithms/tree_matching_1130.cpp b/06_tree_algorithms/tree_matching_1130.cpp
new file mode 100644
index 0000000..8828f68
--- /dev/null
+++ b/06_tree_algorithms/tree_matching_1130.cpp
@@ -0,0 +1,41 @@
+#include <iostream>
+#include <vector>
+
+int f(const std::vector<std::vector<int>>& a,
+    std::vector<std::vector<int>>& t, int v, int p, bool x) {
+	if (t[v][x] != -1) return t[v][x];
+	if (p != -1 && a[v].size() == 1) return t[v][x] = 0;
+
+	t[v][x] = 0;
+	for (auto u : a[v]) {
+		if (u == p) continue;
+		t[v][x] += f(a, t, u, v, false);
+	}
+	if (x) return t[v][x];
+
+	for (auto u : a[v]) {
+		if (u == p) continue;
+		if (f(a, t, u, v, true) == t[u][false]) {
+			t[v][x]++;
+			break;
+		}
+	}
+	return t[v][x];
+}
+
+int main() {
+	int n, x, y;
+	std::cin >> n;
+	std::vector<std::vector<int>> a(n);
+	for (int i = 0; i < n-1; i++) {
+		std::cin >> x >> y;
+		a[x-1].push_back(y-1);
+		a[y-1].push_back(x-1);
+	}
+	if (n == 1) {
+		std::cout << "0\n";
+		return 0;
+	}
+	std::vector<std::vector<int>> t(n, {-1, -1});
+	std::cout << f(a, t, 0, -1, false) << "\n";
+}
-- 
cgit v1.3