{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"\u003cp\u003e\r\nThere is an unrooted tree, \u003cb\u003eT\u003c/b\u003e, with \u003cb\u003eL\u003c/b\u003e leaves and \u003cb\u003eN\u003c/b\u003e nodes. \r\n(Leaves are nodes with degree \u003d 1.) \u003c/p\u003e\r\n\u003cp\u003e\r\nFor every node \u003cb\u003eu\u003c/b\u003e, we define its \u003cb\u003erootScore\u003c/b\u003e.\r\nTo calculate \u003cb\u003erootScore(u)\u003c/b\u003e, first root the tree at \u003cb\u003eu\u003c/b\u003e (which might be a leaf node). \r\n\u003c/p\u003e\u003cp\u003e\r\nWe also define a coloring procedure for any rooted tree. First remove any existing color from all the nodes. Then select some nodes and apply the \u003cb\u003ecolorSubtree\u003c/b\u003e function on them. \r\nWhen \u003cb\u003ecolorSubtree\u003c/b\u003e is called on any node\u003cb\u003e u\u003c/b\u003e, it colors the entire subtree of \u003cb\u003eu\u003c/b\u003e, including \u003cb\u003eu\u003c/b\u003e. \u003c/p\u003e\r\n\u003cp\u003e\r\nYou need to color \u003cb\u003e\"exactly\" floor(L / 2)\u003c/b\u003e of the leaves.\r\nSo, for any root node \u003cb\u003eu\u003c/b\u003e, you will get a set of nodes, \u003cb\u003eS\u003c/b\u003e, such that applying \u003cb\u003ecolorSubtree\u003c/b\u003e on each of its elements will result in exactly \u003cb\u003efloor(L / 2)\u003c/b\u003e the leaves to be colored. \u003c/p\u003e\u003cp\u003e\r\nNote that such a set always exist because one can always choose any of \u003cb\u003efloor(L / 2)\u003c/b\u003e leaves that are not root and put them in \u003cb\u003eS\u003c/b\u003e. \u003c/p\u003e\r\n\u003cp\u003e\r\n\u003cb\u003erootScore(u)\u003c/b\u003e is the minimum cardinality for such a set if \u003cb\u003eu\u003c/b\u003e is the root of the tree.\r\nWhat is the minimum \u003cb\u003erootScore\u003c/b\u003e across all the nodes in \u003cb\u003eT\u003c/b\u003e? \r\n\u003c/p\u003e\r\n\r\n\r\n\u003ch3\u003eInput\u003c/h3\u003e\r\n\u003cul\u003e\r\n\u003cli\u003eFirst line contains \u003cb\u003eN\u003c/b\u003e, the number of nodes in tree \u003cb\u003eT\u003c/b\u003e.\r\n\u003cli\u003eThe next \u003cb\u003eN-1\u003c/b\u003e lines contain \u003cb\u003e2\u003c/b\u003e space separated integers, \u003cb\u003eu\u003c/b\u003e and \u003cb\u003ev\u003c/b\u003e, each denoting that there is an edge between vertex \u003cb\u003eu\u003c/b\u003e and vertex \u003cb\u003ev\u003c/b\u003e.\u003c/ul\u003e\r\n\r\n\u003ch3\u003eOutput\u003c/h3\u003e\r\nOutput a single integer, the answer to the problem.\r\n\r\n\u003ch3\u003eConstraints\u003c/h3\u003e\r\n\u003cul\u003e\r\n\u003cli\u003e\u003cb\u003e1 ≤ N ≤ 3000\u003c/b\u003e\r\n\u003cli\u003e\u003cb\u003e 1 ≤ u, v ≤ N \u003c/b\u003e\r\n\u003c/ul\u003e\r\n\r\n\u003ch3\u003eExample\u003c/h3\u003e\r\n\u003cpre\u003e\u003cb\u003eInput:\u003c/b\u003e\r\n3\r\n2 1\r\n1 3\r\n\r\n\u003cb\u003eOutput:\u003c/b\u003e\r\n1\r\n\u003c/pre\u003e\r\n"}}]}