8553: Maex

You are given a rooted tree consisting of n vertices numbered from 1 to n, and the root is vertex $1$.

Vertex i has a natural number weight ai, and $\text{no two different vertexes have the same weight}$.

Define bu=MEX x ∣ ∃v∈subtree(u),x=av}.

Unfortunately, ai are not given. Please find out the maximum possible ∑i=1nbi.

The$\text{MEX}$ of a set is the minimum non-negative integer that doesn't belong to the set.

The first line contains one integer $T\left(1\le T\le 10\right)$, indicating the number of test cases.

For each test case:

The first line contains one integer n(1≤n≤5⋅105), indicating the number of nodes.

In the following n-1 lines, each line contains two interger $u,v\left(1\le u,v\le n\right)$, indicating an edge $\left(u,v\right)$ of the tree.

A guarantee is that forming trees.

3
5
1 2
3 2
1 5
4 1
3
1 2
2 3
1

8
6
1