Maximum Delayed Requests Importance in a Tree Network

A simple network system can be modeled as an undirected tree. Each node represents a server, and each edge represents a cable connecting two servers. When two servers exchange data, the data travels along the unique simple path connecting them (including both endpoints). Each data exchange request has a non‐negative importance value. More important requests should be processed with higher priority. Moreover, if at some moment there exists a data exchange request with infinite importance and huge amount of data, then every server along its path will process it with priority and block, thereby delaying other requests that pass through any of those servers.

You are the administrator of the network system. The system operates using a sequence of events; at each moment exactly one of the following occurs:

• A new data exchange request appears between two servers.
• An existing data exchange request ends.

All usual requests have data volumes that are small enough to ignore. Your task is: after each event, if a new very important (infinite‐importance) and huge data volume request suddenly appears (whose path can be chosen arbitrarily), compute the maximum possible sum of the importance values of the active requests that would be delayed (i.e. whose paths intersect the chosen path).

Note: The new huge request may choose any simple path in the tree. A request is delayed if its path and the chosen path share at least one common node.

Mathematical formulation:
Let the tree have n nodes. There are active requests, where each request r is defined by its endpoints u_r and v_r and has importance w_r ≥ 0. Denote by P_r the set of vertices along the unique path between u_r and v_r in the tree. For any simple path P in the tree, let S(P) = \sum_{r: P \cap P_r \neq \emptyset} w_r. You need to output \[ \max_{P \text{ is a simple path}} S(P). \]

inputFormat

The first line contains an integer T (T ≥ 1), the number of test cases. For each test case:

1. The first line contains two integers n and m (1 ≤ n ≤ 100, m ≥ 1), the number of servers and the number of events, respectively.
2. Then follow n − 1 lines, each containing two integers u and v (1 ≤ u,v ≤ n), representing an edge between servers u and v.
3. Then follow m lines, each describing an event. An event is in one of the following two formats:
   • 1 u v w – a new data exchange request appears between servers u and v with importance w (0 ≤ w ≤ 10⁹). The requests are assigned consecutive IDs starting from 1 in the order they appear.
   • 2 id – the data exchange request with ID id finishes.

After each event, you should output the maximum possible sum of importances delayed if the huge request appears.

Example Input:

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

Explanation for Test Case 1:

• Servers: 5, with edges: 1–2, 2–3, 2–4, 4–5.
• Event 1: Add request 1 between 1 and 3 with importance 5. Its path is {1,2,3}. Maximum delayed sum = 5.
• Event 2: Add request 2 between 5 and 3 with importance 3. Its path is {5,4,2,3}. Choosing a vertex like 2 or 3 delays both requests, total = 8.
• Event 3: Remove request 1. Only request 2 remains, so answer = 3.
• Event 4: Add request 3 between 1 and 5 with importance 4. Now, the best choice delays both active requests (request 2 and request 3) with total 7.
• Event 5: Remove request 2. Only request 3 remains, so answer = 4.

outputFormat

For each test case, output m lines. Each line contains one integer: the maximum possible sum of importances of delayed requests after that event.

sample

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

5
8
3
7
4
10
15
5
3
10
3
5

</p>