Background

PA 2024 4A

Problem Description

This problem is translated from PA 2024 Round 4 Kolorowy las. Thanks to Macaronlin for providing the translation.

You are given a forest with $n$ vertices (an undirected acyclic graph). The vertices are numbered from $1$ to $n$. Each edge has a positive integer weight. Each vertex has a color, and initially all vertex colors are $0$.

There are $q$ operations of $4$ types:

• $1\ a_i\ b_i\ d_i$: Add an edge of weight $d_i$ between $a_i$ and $b_i$ (it is guaranteed that the graph is still acyclic after adding the edge).
• $2\ a_i\ b_i$: Delete the edge between $a_i$ and $b_i$.
• $3\ v_i\ z_i\ k_i$: Recolor all vertices that are reachable from $v_i$ and whose distance to $v_i$ is at most $z_i$ to color $k_i$.
• $4\ u_i$: Query the color of vertex $u_i$.

Input Format

The first line contains three integers $n,m,q\ (2\le n\le 200\,000,0\le m\le n-1,1\le q\le 200\,000)$, representing the number of vertices, the number of edges, and the number of operations.

The next $m$ lines each contain three integers $a_i,b_i,d_i\ (1\le a_i,b_i\le n,1\le d_i\le 10^9)$, indicating that there is an edge of length $d_i$ between vertices $a_i$ and $b_i$.

The next $q$ lines describe the operations in the format given in the description. It is guaranteed that $1\le a_i,b_i,v_i,u_i\le n$, $1\le d_i\le 10^9$, $0\le z_i\le 10^{15}$, and $1\le k_i\le 10^9$.

It is guaranteed that the given $m$ edges form a valid forest, and after all modifications the graph still forms a valid forest. It is also guaranteed that no operation deletes an edge that does not exist in the graph.

In addition, it is guaranteed that there is at least one operation of type $4$.

Output Format

For each operation of type $4$, output one line with one integer, the answer.

4 2 9
1 2 2
3 2 5
4 2
3 2 2 5
4 1
3 2 4 3
4 1
4 3
2 2 1
1 1 4 1
4 4

0
5
3
0
0

Hint

• In some subtasks, there are no operations of type $1$ and $2$, and $m=n-1$.
• In some subtasks, all operations of type $3$ satisfy $z_i=10^{15}$.

For each of the additional constraints above, there is at least one subtask that satisfies it. The sets of subtasks satisfying the two additional constraints may overlap or may be disjoint.

Translated by ChatGPT 5