Well, it's a pretty easy problem. You should maintain a queue of vertices with degree equal to 1 and add their neighbours to the answer, decrease the neighbour's neighbours' degree by 1 and add those which get degree equal to 1 to the queue.

Its a tree .... so it is bipartite. So maximum matching is the answer. As n = 100000, we can use Hopcroft–Karp Bipartite Matching. I got AC using Bipartite Matching.

Actually, this is a DP problem. Let DP[i][0] be the cost of solving the subtree rooted at i when i itself is not selected, and DP[i][1] be the cost of solving the subtree rooted at i when i is selected. If we don't select i, we must select all its children, otherwise there will be edges with no selected vertex. If we select i, we can freely choose whether or not to select their children when we solve those subtrees. Then...

In the formulas above, c represents the set of children of node i. The answer we seek will be the minimum of DP[1][0] and DP[1][1], assuming we root our tree at node 1.