Corruption in Freedonia

All submissions for this problem are available.
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$ nodes and $N1$ edges. The nodes are numbered from $1$ to $N$, and the tree is rooted at node $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$. Gru believes in divide and conquer and thinks that this network needs to be divided into as many subnetworks as possible. He commands the minions to kill some of the corrupt officials in order to break the network into maximum subnetworks. 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$ officials till the $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$ 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 subnetworks. 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$ $connected$ $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$ $no.$ $of$ $connected$ $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$, number of nodes in the tree.  Next $N1$ lines contains 2 integers $U$, $V$ denoting the endpoints of the $i^{th}$ edge. ###Output:  Print the maximum number of connected components you can obtain after doing the operation any number of times. ###Constraints  $1 \leq N \leq 10^6$  $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.Author:  panik 
Editorial  https://discuss.codechef.com/problems/MINIKILL 
Tags  dfs, graphtheory, panik, plit2020 
Date Added:  21122019 
Time Limit:  2 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, SQL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, R, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 