Fault-Tolerant Request Monitoring in a Tree Network

A simple network system is described by an unrooted tree in which each node represents a server, and each edge represents a data line connecting two servers. Data exchange between two servers travels along the unique simple path connecting them, and every request has an associated importance value. A request is considered affected if any server along its path is faulty. Note that when a server fault occurs, the server is immediately repaired, but the fault still disrupts the currently ongoing data exchanges that include that server.

The system processes events sequentially. At any moment, only one of the following events may occur:

1. A new data exchange request is initiated between two servers with a given importance.
2. An ongoing data exchange request finishes.
3. A server experiences a fault. Immediately after this event, you are required to output the maximum importance among all unaffected and ongoing data exchange requests. (A request that has ended is not considered.)

A request is unaffected by a fault at server x if and only if the unique path between its two endpoints does not contain x. In mathematical terms, if a request is from server u to server v, then server x does not affect the request if and only if \[ d(u,v) \neq d(u,x) + d(x,v), \] where \(d(a,b)\) is the distance between nodes a and b in the tree.

Input Format:

• The first line contains an integer \(n\) representing the number of servers.
• The next \(n-1\) lines each contain two integers \(u\) and \(v\) indicating there is an edge between servers \(u\) and \(v\).
• The following line contains an integer \(Q\) representing the number of events.
• Each of the next \(Q\) lines represents an event in one of the following formats:
  • 1 u v w: A new data exchange request is initiated between servers \(u\) and \(v\) with importance \(w\). The requests are numbered in the order they appear, starting from 1.
  • 2 id: The data exchange request with number \(id\) ends.
  • 3 x: A fault occurs at server \(x\). For this event, output the maximum importance among all active requests that are not affected by this fault. If there is no such request, output \(-1\).

Output Format:

• For each event of type 3, output a single integer on a new line: the maximum importance among the unaffected active requests, or \(-1\) if none exists.

Note: You should use the formula for the distance between two nodes \(a\) and \(b\) in a tree:
\[ d(a,b) = depth(a) + depth(b) - 2 \cdot depth(\text{lca}(a,b)) \]

inputFormat

The first line contains an integer \(n\) (number of servers). The next \(n-1\) lines each contain two integers \(u\) and \(v\), representing the edges in the tree. The following line contains \(Q\) (number of events). Each of the next \(Q\) lines describes an event:

• For a new request: 1 u v w
• For ending a request: 2 id
• For a fault: 3 x

Requests are numbered in the order they are received (starting from 1).

outputFormat

For each event of type 3 (fault event), output a line containing a single integer: the maximum importance among the active requests whose communication paths are not affected by the fault. If no such request exists, output \(-1\).

sample

5
1 2
2 3
2 4
1 5
6
1 1 3 10
1 4 5 7
3 2
2 1
3 1
3 4

-1
-1
-1

</p>