I am the Lorax, and I speak for the Trees!
Plant many of them, plant many now please,
We all live in Thneedville, a connected component,
that has $n$ nodes and $n -1$ edges this moment,
$q$ times we'll make $x_i$ seeds and the same number of pots,
but in different places, believe it or nots.
Match each seed with a pot, and each pot with a seed
But match in a way that's special indeed:
The total sum of the distances between every pair
must be minimized to keep clean the air.
But if $x_i$ is zero and there is no objection,
we'd like you to answer the following question:
If you were to match everything now in the way you've been told
How many pairs would cross this given road?
**This problem has the same idea, data, and samples (but different flavor-text) as another problem written for a training camp by Travis Meade, and tested by myself. Seems to me to be a notorious coincidence. :)
The first line will contain a single integer $c$: the number of test cases.
For each testcase, the first line contains $n$ and $q$: the number nodes in Thneedville, and the number of queries. $n -1$ lines follow, each containing a pair of integers describing the edges in Thneedville.
$q$ lines follow, each of the form $a$ $b$ $x_i$ . If $x_i$ is zero, we are asking about the number of matched pairs that cross the edge from $a$ to $b$ (there will always be an edge directly connecting $a$ to $b$). Otherwise, it indicates that we have created $x_i$ seeds at node $a$, and $x_i$ pots at node $b$.
$c <= 20$
$1 <= n, q <= 10^5$
$1 <= a, b <= n$
$0 <= x_i <= 10^8$
For each query in which $x_i$ is zero, print a single integer: the number of pairs crossing the queried edge.
## Input
The first line will contain a single integer $c$: the number of test cases.For each testcase, the first line contains $n$ and $q$: the number nodes in Thneedville, and the number of queries. $n -1$ lines follow, each containing a pair of integers describing the edges in Thneedville.$q$ lines follow, each of the form $a$ $b$ $x_i$ . If $x_i$ is zero, we are asking about the number of matched pairs that cross the edge from $a$ to $b$ (there will always be an edge directly connecting $a$ to $b$). Otherwise, it indicates that we have created $x_i$ seeds at node $a$, and $x_i$ pots at node $b$.$c <= 20$$1 <= n, q <= 10^5$$1 <= a, b <= n$$0 <= x_i <= 10^8$
## Output
For each query in which $x_i$ is zero, print a single integer: the number of pairs crossing the queried edge.
[samples]
**Definitions**
Let $ G = (V, E) $ be a tree with $ |V| = n $, $ |E| = n-1 $.
Let $ \mathcal{Q} = \{(a_i, b_i, x_i) \mid i \in \{1, \dots, q\}\} $ be a sequence of queries.
**Constraints**
1. $ 1 \le c \le 20 $
2. $ 1 \le n, q \le 10^5 $
3. For each edge $ (a,b) \in E $, $ 1 \le a, b \le n $
4. For each query: $ 0 \le x_i \le 10^8 $
**Objective**
For each query $ (a, b, x_i) $:
- If $ x_i > 0 $: add $ x_i $ seeds at node $ a $ and $ x_i $ pots at node $ b $.
- If $ x_i = 0 $: compute the number of seed-pot pairs $ (s, p) $ such that the unique path from $ s $ to $ p $ in $ G $ crosses the edge $ (a,b) $, under the optimal matching that minimizes total distance.
**Key Insight**
In a tree, the optimal matching minimizing total distance pairs seeds and pots such that the number of pairs crossing an edge $ e = (u,v) $ is:
$$
\min(\text{seeds on } u\text{-side}, \text{pots on } u\text{-side}) + \min(\text{seeds on } v\text{-side}, \text{pots on } v\text{-side})
$$
But since seeds and pots are added in equal numbers and matched optimally (greedily by subtree balance), the number of pairs crossing edge $ (a,b) $ is:
$$
\left| S_a - P_a \right|
$$
where $ S_a $ is total seeds on the side of $ a $ (excluding $ b $), and $ P_a $ is total pots on the side of $ a $, **after all updates**.
**Formal Output for Query $ (a, b, 0) $:**
Let $ T_a $ be the connected component containing $ a $ after removing edge $ (a,b) $.
Let $ S_a = \sum_{\text{seeds added at nodes in } T_a} x_i $,
$ P_a = \sum_{\text{pots added at nodes in } T_a} x_i $.
Then the number of matched pairs crossing $ (a,b) $ is:
$$
\left| S_a - P_a \right|
$$