P10974 Accumulation Degree

Trees are an important part of natural landscapes because they prevent soil erosion and provide a specific climate-shelter ecosystem in and under their leaves. Studies show that trees play an important role in producing oxygen and reducing carbon dioxide in the atmosphere, and they can also regulate ground temperature. They are also important elements in landscape design and agriculture, both for their aesthetic appeal and for their orchard crops (such as apples). Wood is also a common building material.

Trees also play a close role in many world myths. Many researchers are interested in some special properties of trees, such as the center of a tree, counting trees, coloring trees, and so on. The accumulation degree $A(x)$ is one such property. We define $A(x)$ as follows: - Each edge of the tree has a positive capacity. - Nodes with degree $1$ in the tree are called terminal nodes. - The flow on each edge cannot exceed its capacity. - $A(x)$ is the maximum amount of flow that node $x$ can send to other terminal nodes. The accumulation degree of a tree is the maximum accumulation degree among all its nodes. Your task is to find the accumulation degree of the given tree.

The first line contains an integer $T$, the number of test cases. For each test case, the first line contains a positive integer $n$. Each of the next $n - 1$ lines contains three integers $x, y, z$ separated by spaces, meaning there is an edge between node $x$ and node $y$ with capacity $z$. Nodes are numbered from $1$ to $n$. All values are non-negative integers not exceeding $200000$. You may assume the testdata always forms a tree.

For each test case, output the answer on a separate line.

Constraints not mentioned in the original statement: $T \le 4$, $\sum n \le 2\times 10 ^ 5$. Translated by ChatGPT 5