Background

Original link: https://oier.team/problems/X6H.

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

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?

Problem Description

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.

Input Format

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$.

Output Format

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

5 3
1 2 1
2 3 1
3 4 1
4 5 1
1 4 3 5 1
2 1 5 1
1 1 1 3 100

1
1
3

6 12
3 5 18
3 1 8
5 6 3
6 4 10
6 2 8
1 4 3 4 10
1 5 6 2 5
2 2 5 1
1 7 3 2 19
2 4 6 1
1 3 5 6 20
2 3 4 1
1 9 5 6 16
2 3 1 32
2 3 4 30
2 3 5 22
2 3 2 21

0
0
0
8
8
8
8
8
12
19
19
40

Hint

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