1230-Placing_Lampposts.cpp

#include <bits/stdc++.h>
#define ll long long
#define MAX 100100

using namespace std;

ll visited[1010];
ll dp[1010][2];
ll dpcountr[1010][2];
vector <ll > edge[1010];

ll dfs(ll curr, ll taken, ll prev)
{
	visited[curr] = 1;

	if (edge[curr].size() == 1 and edge[curr][0] == prev) {
		if (taken == 1)
			return 1;
		else
			return 0;
	}

	if (dp[curr][taken])
		return dp[curr][taken];

	ll ans = 0;
	dpcountr[curr][taken]  = 0;

	if (taken == 0) {
		for (int i = 0; i < edge[curr].size(); i++) {
			if (edge[curr][i] != prev) {
				ans += dfs(edge[curr][i], 1 , curr);
				dpcountr[curr][taken] += dpcountr[edge[curr][i]][1];
			}
		}

	} else {
		ans = 1;

		for (int i = 0; i < edge[curr].size(); i++) {
			if (edge[curr][i] != prev) {
				ll a1 = dfs(edge[curr][i], 0 , curr);
				ll a2 = dfs(edge[curr][i], 1 , curr);

				if (a1 < a2) {
					ans += a1;
					dpcountr[curr][taken] += dpcountr[edge[curr][i]][0];

				} else if (a2 < a1) {
					ans += a2;
					dpcountr[curr][taken] += 1 +  dpcountr[edge[curr][i]][1];

				} else {
					ans += a2;
					dpcountr[curr][taken] += max(dpcountr[edge[curr][i]][0], 1 +  dpcountr[edge[curr][i]][1]);
				}
			}
		}
	}

	return  dp[curr][taken] = ans;
}


int main()
{
#ifndef ONLINE_JUDGE
	freopen("/home/sameer/Documents/sameer/input.sam", "r", stdin);
#endif
	ios_base::sync_with_stdio(false);
	ll i, j, k, n, m, t, cont, a, b;
	cin >> t;
	ll cases = t;

	while (t--) {
		cin >> n >> m;
		memset(visited, 0, sizeof visited);
		memset(dp, 0, sizeof dp);
		memset(dpcountr, 0, sizeof dpcountr);

		for (i = 0; i < 1010; i++)
			edge[i].clear();

		for (i = 0; i < m; i++) {
			cin >> a >> b;
			edge[a].push_back(b);
			edge[b].push_back(a);
		}

		ll ans = 0;
		ll cnt = 0;

		for (i = 0; i < n; i++) {
			if (visited[i] == 0) {
				ll a1 = dfs(i, 0, -1);
				ll a2 = dfs(i, 1, -1);

				if (a1 < a2) {
					ans += a1;
					cnt += dpcountr[i][0];

				} else if (a2 < a1) {
					ans += a2;
					cnt += dpcountr[i][1];

				} else {
					ans += a1;
					cnt += max(dpcountr[i][0], dpcountr[i][1]);
				}
			}
		}

		cout << "Case " << cases - t << ": "  << ans << " "  << cnt << " " <<  m - cnt << endl;
	}

	return 0;
}