P11161 [MX-X6-T7] Summer Ends (Natsu ga Owaru)

Original link: . --- > _Knowing the end of summer$\\$ We are reflected in the drops of ramune$\\$ As if we might lose sight of it$\\$ Chasing those sunset-red cheeks$\\$ We will come back here again next year_ > > _—— [Natsu ga Owaru - Nanatsukaze](https://music.163.com/#/song?id=2614276904)_ A year passes, you walk a full loop, and return to the starting point. In this world of nonstop change, will there still be a chance to meet you again? When choosing an optimal path, how big is that chance?

Given a tree $T$ with $n$ nodes, with weighted edges. Define an undirected complete graph $G(T)$: - It contains $n$ nodes. - If $T$ contains an edge $u,v$, then the weight of edge $u,v$ in $G$ is the weight of that edge; otherwise it is $0$. Let $w(T)$ be the weight of the minimum-weight Hamiltonian cycle in $G(T)$. You are given $q$ modification operations, of two types: - Delete one edge in $T$ and then add one edge, **guaranteeing that after each operation it is still a tree**. - Given a path in $T$, increase the weight of every edge on that path by a value. You need to compute $w(T)$ after each operation.

The first line contains two positive integers $n,q$. The next $n-1$ lines each contain three positive integers $u,v,w$, describing an edge in the tree. The edges are numbered $1\sim n-1$ in the input order. The next $q$ lines each contain $4$ or $5$ integers. The first integer is the operation type $opt$: - If $opt=1$, it means a delete-edge-then-add-edge operation. The next $4$ integers are $i,u,v,w$ in order: $i$ is the index of the edge deleted in this operation; $u,v,w$ describe the new edge added. These newly added edges are numbered consecutively in the operation order starting from $n$. - If $opt=2$, it means a path-add operation. The next $3$ integers are $u,v,w$: increase the weight of every edge on the simple path between $u$ and $v$ in the tree by $w$.

Print $q$ lines, each containing one integer: the value of $w(T)$ after the corresponding operation.

**Sample Explanation #1** After the first operation, the shape of $G(T)$ is as follows:  The tree edges are marked in red. One of the optimal Hamiltonian cycles is $1-5-4-2-3-1$. **Constraints** For all testdata, it is guaranteed that $5\leq n\leq 1.5\times 10^5$, $1\leq q\leq 3\times 10^5$, $1\leq u,v\leq n$, $1\leq w\leq 2\times 10^{11}$. It is guaranteed that at any time the edge weight does not exceed $4\times 10^{11}$. It is guaranteed that an edge that has already been deleted will not be deleted again. **Bundled tests**, with 5 subtasks. The detailed limits are as follows: - Subtask 1 (6 pts): $n\leq 10$, $q\leq 500$. - Subtask 2 (27 pts): $n,q\leq 2000$. - Subtask 3 (15 pts): all answers are $\geq 1$. - Subtask 4 (26 pts): $n\leq 7.5\times 10^4$, $q\leq 1.5\times 10^5$. - Subtask 5 (26 pts): no special limits. Translated by ChatGPT 5