G is bipartite since it is a tree. Try to separate the two vertex sets and look at the edges that join them. Once you do that you should be able to count edges really easily using a pile of different algorithms.

You need an algorithm to find out what it's algorithmic complexity is. But this problem is definitely polynomial.