D. Mex Tree
brute force; dp; trees
You are given a tree with \(n\) nodes. For each node, you either color it in \(0\) or \(1\).The value of a path \((u,v)\) is equal to the MEX\(^\dagger\) of the colors of the nodes from the shortest path between \(u\) and \(v\).The value of a coloring is equal to the sum of values of all paths \((u,v)\) such that \(1 \leq u \leq v \leq n\).What is the maximum possible value of any coloring of the tree?\(^{\dagger}\) The MEX (minimum excluded) of an array is the smallest non-negative integer that does not belong to the array. For instance: The MEX of \([2,2,1]\) is \(0\), because \(0\) does not belong to the array. The MEX of \([3,1,0,1]\) is \(2\), because \(0\) and \(1\) belong to the array, but \(2\) does not. The MEX of \([0,3,1,2]\) is \(4\) because \(0\), \(1\), \(2\), and \(3\) belong to the array, but \(4\) does not.
Each test contains multiple test cases. The first line of input contains a single integer \(t\) (\(1 \le t \le 10^4\)) — the number of test cases. The description of test cases follows.The first line of each test case contains a single integer \(n\) (\(1 \le n \le 2 \cdot 10^5\)) — the number of nodes in the tree.The following \(n-1\) lines of each test case contains \(2\) integers \(a_i\) and \(b_i\) (\(1 \leq a_i, b_i \leq n, a_i \neq b_i\)) — indicating an edge between vertices \(a_i\) and \(b_i\). It is guaranteed that the given edges form a tree.It is guaranteed that the sum of \(n\) across all test cases does not exceed \(2 \cdot 10^5\).
For each test case, print the maximum possible value of any coloring of the tree.
In the first sample, we will color vertex \(2\) in \(1\) and vertices \(1,3\) in \(0\). After this, we consider all paths: \((1,1)\) with value \(1\) \((1,2)\) with value \(2\) \((1,3)\) with value \(2\) \((2,2)\) with value \(0\) \((2,3)\) with value \(2\) \((3,3)\) with value \(1\) We notice the sum of values is \(8\) which is the maximum possible.