P4315 Moonlit "Maojing Tree"

After a timely transformation, the caterpillar narrowly escaped and left the vegetable garden. It traveled over mountains and rivers, through countless hardships, and finally arrived at the campus of Shaoxing No. 1 High School.

Crawl, crawl~ crawl, crawl~~ The caterpillar crawled under a small "Maojing Tree" and found that it bore its favorite maomao fruits. The "Maojing Tree" has $N$ nodes and $N-1$ edges. There are no maomao fruits on the nodes; all maomao fruits grow on the edges. This "Maojing Tree" has magical power: it can change the number of maomao fruits on its edges: - `Change k w`: Set the number of maomao fruits on the $k$-th edge to $w$. - `Cover u v w`: Set the number of maomao fruits on every edge along the path between nodes $u$ and $v$ to $w$. - `Add u v w`: Increase by $w$ the number of maomao fruits on every edge along the path between nodes $u$ and $v$. Since the caterpillar is greedy, it will ask the following query: - `Max u v`: Query the maximum number of maomao fruits among all edges along the path between nodes $u$ and $v$.

The first line contains a positive integer $N$. The next $N-1$ lines each contain three positive integers $U_i$, $V_i$, and $W_i$. The $(i+1)$-th line describes the $i$-th edge: it connects nodes $U_i$ and $V_i$, and there are $W_i$ maomao fruits on that edge. Then follow the operations and queries, one per line, terminated by a single line `Stop`.

For each `Max` query, output its answer on a separate line.

For all testdata, $1 \le N \le 10^5$, and the total number of operations and queries does not exceed $10^5$. It is guaranteed that at any time, the number of maomao fruits on every edge does not exceed $10^9$. Translated by ChatGPT 5