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
  30. 30
  31. 31
  32. 32
  33. 33
  34. 34
  35. 35
  36. 36
  37. 37
  38. 38
  39. 39
  40. 40
  41. 41
  42. 42
  43. 43
  44. 44
#include <bits/stdc++.h>
#define f first
#define s second
#define eb emplace_back
using namespace std;
using ll = long long;
using ii = pair<int, int>;
constexpr int MAXN = 100001;
constexpr ll INF = 1e9;

int N, Q, H[MAXN];
bitset<MAXN> ans;
vector<ii> G[3 * MAXN];
unordered_map<ll, int> vis;

void solve(int u, int p, int d) {
	if (d && u <= N) ans[u] = 1;
	if (d < 0) d = -1;
	if (vis.find(INF * u + p) != vis.end()) {
		if (vis[INF * u + p] != d) d = -1;
		else return;
	}
	vis[INF * u + p] = d;
	for (auto & v : G[u]) if (v.s != p) solve(v.s, u, d - v.f);
}

int main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	cin >> N >> Q;
	iota(H, H + N + 1, 0);
	int l = N + 1;
	for (int i = 1, a, b; i < N; ++i) {
		cin >> a >> b;
		G[H[a]].eb(0, l), G[l].eb(0, H[a]), H[a] = l++;
		G[H[b]].eb(0, l), G[l].eb(0, H[b]),	H[b] = l++;
		G[H[a]].eb(1, H[b]), G[H[b]].eb(1, H[a]);
	}
	while (Q--) {
		int a, b; cin >> a >> b;
		solve(a, 0, b);
	}
	cout << N - ans.count() << '\n';
	for (int i = 1; i <= N; ++i) if (!ans[i]) cout << i << '\n';
}