Optimal Splitting

All submissions for this problem are available.
Given a tree with n nodes. Split it into 3 parts such that all the three parts are connected components in original graph and each node is exactly present in one of the parts and the following function is minimised: Let s1,s2,s3 be the sizes of the 3 parts (or connected components) then $f=s1s2+s2s3+s1s3$ Also calculate the number of ways of splitting the tree. Two ways are considered different if different sets of edges is removed. ###Input:  First line will contain $n$, number of vertices in the tree.  Each of the next $n1$ lines contain two space separated integers $u$ and $v$ denoting an edge between u and v ###Output: Output in a single line two space centered integers denoting the optimal value of function and number of ways to achieve it. ###Constraints  $3 \leq n \leq 100000$ ###Sample Input 1: 5 1 2 2 3 3 4 4 5 ###Sample Output 1: 2 3 ###Sample Input 2: 9 1 2 1 3 3 4 3 5 4 6 4 7 5 8 5 9 ###Sample Output 2: 0 1 ###EXPLANATION: For first input, Optimum Splitting=[1]+[2,3]+[4,5] or [1,2]+[3]+[4,5] or [1,2]+[3,4]+[5] Hence number of ways=3 and f=21+22+21=2 For second, Optimum Splliting=[1,2,3]+[4,6,7]+[5,8,9] Hence number of ways=1 and f=33+33+33=0Author:  kalpitk 
Tags  kalpitk 
Date Added:  23032019 
Time Limit:  1 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, 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. 