f (v) = какая-то функция в вершине v
выберем корень в дереве
f (v) = функция от поддерева вершины v

f (v, 0) = количество выбранных вершин в поддереве v,
           если мы не выбрали v
f (v, 1) = количество выбранных вершин в поддереве v,
           если мы выбрали v

База: (для листьев)
f (v, 0) = 0
f (v, 1) = 1

Пересчёт:
f (v, 1) = sum {u ребёнок v} f (u, 0)                    + 1 (сама вершина v)
f (v, 0) = sum {u ребёнок v} max [ f (u, 0), f (u, 1) ]

Чтение графа:

vector <vector <int> > adj (n);

for (int j = 0; j < m; j++)
{
	int u, v;
	cin >> u >> v;
	u -= 1;
	v -= 1;
	adj[u].push_back (v);
	adj[v].push_back (u);
}

vector <vector <int> f (n, vector <int> (2, 0));

void recur (int v, int p)
{
	f[v][1] = 1;
	f[v][0] = 0;
	for (auto u : adj[v])
	{
		if (u == p) continue;
		recur (u, v);
		f[v][1] += f[u][0];
		f[v][0] += max (f[u][0], f[u][1]);
	}
}

int root = 0;
f (root, -1);
cout << max (f[root][0], f[root][1]) << endl;
