usaco-camp

Short, concise solutions for problems from the USACO camp

  1. 1
  2. 2
  3. 3
  4. 4
  5. 5
  6. 6
  7. 7
  8. 8
  9. 9
  10. 10
  11. 11
  12. 12
  13. 13
  14. 14
  15. 15
  16. 16
  17. 17
  18. 18
  19. 19
  20. 20
  21. 21
  22. 22
  23. 23
  24. 24
  25. 25
  26. 26
  27. 27
  28. 28
  29. 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';
}