P4556 【Template】Segment Tree Merge / [Vani's Date] The Tail of a Rainy Day

Shenhuili has always disliked rainy days. Scorching weather pierced through the first half of summer, then a heavy rain and the ensuing flood extinguished everything. Although the small village of Shenhuili’s hometown had a stubborn resistance to floods, several old houses still collapsed, a few old trees were uprooted, and the crops in the fields were left in a mess. Helpless, Shenhuili and the villagers could only wait for relief rations to survive. However, the distribution method was special.

There are $n$ houses in the village, forming a tree. Relief rations are distributed $m$ times. Each time, two houses $(x, y)$ are chosen. For every house on the path from $x$ to $y$ (including $x$ and $y$), one bag of type $z$ relief rations is given. After all distributions are finished, Shenhuili wants to know, for each house, which type of relief rations is stored the most.

The first line contains two positive integers $n$ and $m$. Lines $2$ through $n$ each contain two integers $a, b$, indicating that there is an edge between houses $a$ and $b$. Lines $(n + 1)$ through $(n + m)$ each contain three integers $x, y, z$, indicating that in one distribution, every house on the path from $x$ to $y$ receives one bag of type $z$ relief rations.

Output $n$ lines. The integer on the $i$-th line is the type of relief rations that appears most in house $i$. If multiple types are tied for the maximum, output the smallest type id. If a house has no relief rations, output 0.

- For $20\%$ of the testdata, it is guaranteed that $n, m \leq 100$. - For $50\%$ of the testdata, it is guaranteed that $n, m \leq 2 \times 10^3$. - For $100\%$ of the testdata, it is guaranteed that $1 \leq n, m \leq 10^5$, $1 \leq a, b, x, y \leq n$, and $1 \leq z \leq 10^5$. Translated by ChatGPT 5