CF2227H Fallen Leaves

Yousef is given a tree $ ^{\text{∗}} $ of $ n $ vertices numbered from $ 1 $ to $ n $ . Let $ S $ be the set of all leaves $ ^{\text{†}} $ of the given tree (this set is determined from the original tree and does not change). Yousef repeats the following process until the number of unchosen vertices is at most one: - Choose two distinct vertices $ u, v \in S $ that have not been chosen before. - Add $ d(u, v) $ to the total cost, where $ d(u, v) $ is the number of edges on the simple path between $ u $ and $ v $ . - Mark $ u $ and $ v $ as chosen. Your task is to help Yousef determine the minimum possible total cost achievable after the process ends. $ ^{\text{∗}} $ A tree is an undirected connected graph in which there are no cycles. $ ^{\text{†}} $ A leaf of a tree is a vertex that is connected to at most one other vertex.

The first line contains an integer $ t $ ( $ 1 \le t \le 10^4 $ ) — the number of test cases. Then $ t $ test cases follow. Each test case consists of several lines. The first line of the test case contains an integer $ n $ ( $ 3 \le n \le 2 \cdot 10^5 $ ) — the number of vertices in the tree. Then $ n − 1 $ lines follow, each of which contains two integers $ u $ and $ v $ ( $ 1 \le u, v \le n $ , $ u \ne v $ ) that describe a pair of vertices connected by an edge. It is guaranteed that the given graph is a tree and has no loops or multiple edges. It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 2 \cdot 10^5 $ .

For each test case, output a single integer — the minimum possible total cost achievable after the process ends.

In the first test case, the set of leaves $ S $ contains $ \{1, 3, 4\} $ . Yousef can do the following: - Choose $ u = 1 $ , $ v = 3 $ , with $ d(1, 3) = 2 $ . Yousef adds $ 2 $ to the total cost and marks vertices $ 1 $ and $ 3 $ as chosen. Since there is one vertex left unchosen, the process stops, and the total cost is $ 2 $ . It can be shown that $ 2 $ is the minimum answer.  The given tree in the first test case.In the second test case, the set of leaves $ S $ contains $ \{1, 3, 5, 6\} $ . Yousef can do the following: - Choose $ u = 1 $ , $ v = 3 $ , with $ d(1, 3) = 2 $ . Yousef adds $ 2 $ to the total cost and marks vertices $ 1 $ and $ 3 $ as chosen. - Choose $ u = 5 $ , $ v = 6 $ , with $ d(5, 6) = 2 $ . Yousef adds $ 2 $ to the total cost and marks vertices $ 5 $ and $ 6 $ as chosen. Since there is no vertex left unchosen, the process stops, and the total cost is $ 4 $ .  The given tree in the second test case.