407029: GYM102694 F The Lorax
Description
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. :)
InputThe 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 \leq 20$$$
$$$1 \leq n, q \leq 10^5$$$
$$$1 \leq a, b \leq n$$$
$$$0 \leq x_i \leq 10^8$$$
OutputFor each query in which $$$x_i$$$ is zero, print a single integer: the number of pairs crossing the queried edge.
ExampleInput2 6 5 1 2 2 3 3 4 4 5 4 6 1 6 2 2 5 3 4 3 0 6 2 2 4 3 0 4 6 1 2 1 3 4 1 1 2 0 3 4 5 4 2 1 1 3 0 1 4 0 1 2 0Output
5 3 0 5 4 1