Corruption is on the rise in the country of Freedonia, Gru's home. Gru wants to end this for good and for that he needs the help of his beloved minions.
This corruption network can be represented in the form of a tree having N$N$ nodes and N−1$N-1$ edges. The nodes are numbered from 1$1$ to N$N$, and the tree is rooted at node 1$1$. These nodes represent the corrupt officials and each corrupt official works under some other corrupt official except the Boss who is represented by node 1$1$.
Gru believes in divide and conquer and thinks that this network needs to be divided into as many sub-networks as possible.
He commands the minions to kill some of the corrupt officials in order to break the network into maximum sub-networks. But as you know, these corrupt officials are very sharp, and hence these assassinations need to be done very smartly and silently, without leaving any traces.  To achieve this Gru devises a strategy, in which he designs an operation, and that operation can be applied by the minions any number of times (even 0). 
In one operation the minions can select any one leaf node official [that is an official who does not have any other official beneath him] in the graph and kill him along with all his ancestors$ancestors$ officials till the root$root$ of the tree in which the operation is applied (this is done to wipe all traces of the operation). This deleted all those nodes from the graph, and also, while doing so, all the associated edges/connections$edges/connections$ of the leaf node and its ancestors are also destroyed. Hence after applying this operation on any tree, it breaks into some connected components which are also trees, which are the new sub-networks.
Now the minions are a bit lazy and will do the task someday, but they need to submit a report to Gru containing the number of the maximum$maximum$ connected$connected$ components$components$ that they could achieve by applying the operation any number of times. To do this, the minions require your help. So help the minions by finding out the maximum$maximum$ no.$no.$ of$of$ connected$connected$ components$components$ that can be achieved.
Note: After each operation, the topmost node (node with the lowest level. It can be proved that there will always be a unique node with the lowest level in each tree) of each of the remaining trees becomes the root of that particular tree (that is, after the first operation it can be visualized that the graph converts into a forest of rooted trees)

-----Input:-----
- First line will contain N$N$, number of nodes in the tree. 
- Next N−1$N-1$ lines contains 2 integers U$U$, V$V$ denoting the endpoints of the ith$i^{th}$ edge.

-----Output:-----
- Print the maximum number of connected components you can obtain after doing the operation any number of times.

-----Constraints-----
- 1≤N≤106$1 \leq N \leq 10^6$
- 1≤U,V≤N$1 \leq U,V \leq N$

-----Sample Input:-----
7
1 2
1 3
2 4
2 5
3 6
3 7

-----Sample Output:-----
2

-----EXPLANATION:-----
We have 4 leaf nodes in this tree: 4 5 6 7. Suppose we delete node 5, then along with it we also delete node 2 and node 1. so after the deletion we are left with 2 trees, one consisting of only node 4 as the root node of that particular tree, and the other consisting of node 3,6,7 with node 3 as the root node. This can also be achieved by deleting any of the other leaf nodes and it can be proved that we cannot obtain more than 2 connected components in this example.

Source: codechef | Difficulty: HARD
Tags: Graph algorithms

Graph traversal

Constructive algorithms


Solutions:
from sys import stdin, stdout
input = stdin.readline
n = int(input())
a = [[] for i in range(n)]
for i in range(n - 1):
	(u, v) = map(int, input().split())
	a[u - 1].append(v - 1)
	a[v - 1].append(u - 1)
b = [0] * n
vis = [0] * n
st = [(0, 0)]
vis[0] = 1
pa = [0] * n
while st:
	(x, y) = st.pop()
	b[x] = y
	for i in a[x]:
		if vis[i] == 0:
			pa[i] = x
			vis[i] = 1
			if x == 0:
				st.append((i, y + len(a[x]) - 1))
			else:
				st.append((i, y + len(a[x]) - 2))
c = []
for i in range(1, n):
	if len(a[i]) == 1:
		c.append((b[i], i))
c.sort()
ans = 0
while c:
	(x, y) = c.pop()
	m = y
	p = 0
	while y != 0 and pa[y] != -1:
		y = pa[y]
		if pa[y] == -1:
			break
		if y != 0:
			p += len(a[y]) - 2
		else:
			p += len(a[y]) - 1
	if p >= 1:
		p = 0
		while m != 0 and pa[m] != -1:
			x = m
			if pa[m] == -1:
				break
			m = pa[m]
			pa[x] = -1
			if m != 0:
				p += len(a[m]) - 2
			else:
				p += len(a[m]) - 1
		if y == 0:
			pa[0] = -1
for i in range(n):
	if pa[i] != -1:
		st = [i]
		pa[i] = -1
		while st:
			x = st.pop()
			for j in a[x]:
				if pa[j] != -1:
					pa[j] = -1
					st.append(j)
		ans += 1
print(ans)


import sys
adj = list()
hm = dict()
sys.setrecursionlimit(10000000)

def cal(i, p):
	if i in hm:
		return hm[i]
	if len(adj[i]) == 1:
		hm[i] = 0
		return hm[i]
	m = 0
	for node in adj[i]:
		if node == p:
			continue
		m = max(m, cal(node, i))
	if m == 0:
		hm[i] = len(adj[i]) - 2
		return hm[i]
	else:
		tmp = 0
		for node in adj[i]:
			if node == p:
				continue
			tmp += max(cal(node, i), 1)
		hm[i] = tmp
		return hm[i]
n = int(input())
for i in range(n):
	adj.append(list())
for i in range(n - 1):
	(a, b) = input().split()
	(a, b) = (int(a) - 1, int(b) - 1)
	adj[a].append(b)
	adj[b].append(a)
adj[0].append(-1)
print(max(cal(0, -1), 1))