Initial commit

3 files changed, 64 insertions, 0 deletions

diff --git a/06_tree_algorithms/a.out b/06_tree_algorithms/a.out
new file mode 100755
index 0000000..ec817fa
--- /dev/null
+++ b/06_tree_algorithms/a.out
diff --git a/06_tree_algorithms/subordinates_1674.cpp b/06_tree_algorithms/subordinates_1674.cpp
new file mode 100644
index 0000000..38982ce
--- /dev/null
+++ b/06_tree_algorithms/subordinates_1674.cpp
@@ -0,0 +1,23 @@
+#include <iostream>
+#include <vector>
+
+int f(const std::vector<std::vector<int>>& a, std::vector<int>& b, int i) {
+        for (auto x : a[i]) 
+                b[i] += f(a, b, x) + 1;
+        return b[i];
+}
+
+int main() {
+        int n, x;
+        std::cin >> n;
+        std::vector<std::vector<int>> a(n);
+        for (int i = 1; i < n; i++) {
+                std::cin >> x;
+                a[x-1].push_back(i);
+        }
+        std::vector<int> b(n, 0);
+        f(a, b, 0);
+        for (auto y : b)
+                std::cout << y << " ";
+        std::cout << std::endl;
+}
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";
+}