1 files changed, 29 insertions, 0 deletions
diff --git a/2020/day6/friend.cpp b/2020/day6/friend.cpp
new file mode 100644
index 0000000..6a9fdec
--- /dev/null
+++ b/2020/day6/friend.cpp
@@ -0,0 +1,29 @@
+#include <bits/stdc++.h>
+#define f first
+#define s second
+using namespace std;
+typedef long long ll;
+typedef pair<int, int> ii;
+constexpr ll MOD = 1e9+7;
+
+int a[100001], b[100001];
+map<ii, ll> f, g;
+
+int main() {
+	int N;
+	cin >> N;
+	f[ii(1, 2)] = 1;
+	for (int i = 3; i <= N; ++i) {
+		cin >> a[i] >> b[i];
+		f[ii(a[i], i)] = f[ii(b[i], i)] = 1;
+	}
+	g = f;
+	int ans = 0;
+	for (int i = N; i >= 3; --i) {
+		ii x(a[i], i), y(b[i], i), z(a[i], b[i]);
+		ans = (g[x] * f[y] % MOD * f[z] + f[x] * g[y] % MOD * f[z] + f[x] * f[y] % MOD * g[z] + ans) % MOD;
+		g[z] = (f[x] * g[y] + g[x] * f[y] + g[z]) % MOD;
+		f[z] = (f[x] * f[y] + f[z]) % MOD;
+	}
+	cout << 2 * ans % MOD << '\n';
+}
+\ No newline at end of file