P9305 "DTOI-5" Withered Trees Outside the School Gate

 Withered trees inside the school gate, 25/02/24. --- One day after school, you walked out of the school gate and found that another row of trees had appeared outside. However, since it was the middle of winter, all the leaves had fallen off. The trees were trembling in the cold wind, making you worry that they might lose balance at some moment and then fall down.

You are given a row of $T$ undirected rooted trees outside the school gate (the root of each tree is node $1$). Each edge of each tree has a weight $m_i$. Now you need to compute the imbalance of each tree **or** the imbalance of the **subtree of every node** in that tree, so that the school can reinforce them. $\color{white}\sout{\text{Don’t ask me why the weight uses the letter }m\text{.}}$ Note that the **edges of the tree are ordered**, ~~you can’t possibly break off a branch and graft it somewhere else, this is a withered tree after all~~. --- For a rooted tree, define its imbalance as follows: choose a shortest path from the root to some leaf node, and use this path to split the tree’s edges into a left part and a right part (two edge sets). (Neither edge set contains any edge on the chosen shortest path.) The imbalance is the minimum possible value of the absolute difference between the total edge weights of the two parts. In particular, the imbalance of a single node (a tree with one node) is $0$. The total weight of an empty edge set is $0$.

The first line contains two positive integers $T, k$, where $T$ is the number of test cases (i.e., the total number of trees). In each test case: - If $k = 1$, you only need to compute the imbalance of the whole tree. - If $k = 2$, **you need to compute the imbalance of the subtree of each node separately**. For each tree, the first line contains a positive integer $n$, the number of nodes in the tree. The next $n$ lines describe the nodes. Line $u$ describes node $u$: - The first positive integer is the number of children of this node, denoted by $x$. - Then there are $2x$ positive integers. The $(2i-1)$-th number is the $i$-th child $v$ of node $u$ **from left to right**, and the $(2i)$-th number is the weight of the edge connecting $u$ and $v$, denoted by $m_{u\leftrightarrow v}$.

Output $T$ lines: - If $k = 1$, line $i$ outputs one non-negative integer, the imbalance of the $i$-th tree. - If $k = 2$, line $i$ outputs $n$ non-negative integers; the $j$-th number is the imbalance of the subtree rooted at node $j$ in the $i$-th tree.

**Constraints** **No bundled testdata**. Within the same $\text{Subtask}$, each test point is equally weighted. $$ %\def\or{\operatorname{or}} %this arraystretch is always misspelled/oh \def\arraystretch{1.5} \begin{array}{|c|c|c|c|c|}\hline \textbf{Subtask}&\sum n\leqslant&k=&\textbf{Special Constraints}&\textbf{Score}\cr\hline \sf1&2\times10^5&1&\bf A&1\cr\hline \sf2&20&1&T=1&5\cr\hline \sf3&5000&1&&5\cr\hline \sf4&10^5&2&\bf B&15\cr\hline \sf5&3\times10^5&1&&30\cr\hline \sf6&2\times10^5&2&\bf A'&4\cr\hline \sf7&3\times10^5&2&&40\cr\hline \end{array} $$ - Special property $\bf A$ ~~width limit 2.6 m~~: Each tree is guaranteed to have exactly one leaf node ($n \geqslant 2$). - Special property $\bf B$ ~~height limit 4.5 m~~: Each tree is guaranteed to be a star (the root has $n-1$ children). - Special property $\bf A'$: Each tree is guaranteed to be a chain (the degree of each node is at most $2$). Difference between $\bf A$ and $\bf A'$: in $\bf A'$, the root may have degree $2$, while in $\bf A$, the root obviously has degree $1$. For $100\%$ of the data: $T \leqslant 4000$, ${\color{red}\textbf1}\leqslant n\leqslant 10^5$, $\sum n\leqslant 3\times10^5$, $1 \leqslant m_i \leqslant 10^4$, $1 \leqslant u, v \leqslant n$, $k \in \{1, 2\}$. --- A leaf node is a node with no children, i.e., a node (except the root) whose degree in the tree is $1$. In the sample input, blank lines are added for readability; there are no blank lines in the actual data. **Explanation for Sample $\bm1-\bm1$** The tree is shown below, and the edge weights are the edge weights.  The optimal solution chooses $1 \to 2 \to 7$ as the splitting path, and the imbalance is ${\large\vert}(2+19+19)-7{\large\vert}=33$. If you choose $1 \to 2 \to 6$ as the splitting path, then the difference between the total edge weights of the two parts is ${\large\vert}(2+19)-(7+514){\large\vert}=500$, which is not minimal. $\color{transparent}\sout{Note that: \begin{cases}114+2+19+19=154\\114+514+19+19=666\end{cases}}$ **Explanation for Sample $\bm1-\bm2$** The tree is shown below.  The optimal solution chooses $1 \to 3 \to 7$ as the splitting path, and the imbalance is ${\large\vert}(4+8+3+6)-(1+7+5+10){\large\vert}=2$。 Translated by ChatGPT 5