Tree Path Distance Sum With Edge Updates

You are given an integer n, a list edges, and a list queries. There are n nodes labeled from 0 to n - 1. Each element in edges contains [u, v, w] meaning there is an edge between node u and node v whose weight is w. The n - 1 edges form a tree, so exactly one path joins any two nodes.

The distance between two nodes is the sum of the weights of the edges on the path between them. The distance from a node to itself is 0.

Each element in queries contains [type, x, y, w], and the queries are processed in the order given:

• [1, x, y, w] sets the weight of the edge between x and y to w. You can assume that edge is in the tree. The two endpoints may be listed in either order.
• [2, x, y, 0] asks for the distance between x and y right now. The fourth value is always 0.

Return the sum of the answers to all queries of the second type.

If there are no queries of the second type, return 0.

Note that the answer can exceed the 32-bit integer range.

Examples

Example 1

Input: n = 3, edges = [[0,1,5],[1,2,7]], queries = [[2,0,2,0],[1,1,2,1],[2,0,2,0]]
Output: 18
Explanation: The first query walks 0 to 1 to 2 for a distance of 5 + 7 = 12. The second query drops the weight of edge (1, 2) to 1. The third query walks the same path, now 5 + 1 = 6. The total is 12 + 6 = 18.

Example 2

Input: n = 4, edges = [[0,1,2],[0,2,3],[2,3,4]], queries = [[2,1,3,0],[2,1,1,0],[1,0,2,10],[2,1,3,0]]
Output: 25
Explanation: The path from 1 to 3 is 1 to 0 to 2 to 3, so the first query gives 2 + 3 + 4 = 9. The second query asks about a node and itself, which is 0. The third query raises the weight of edge (0, 2) from 3 to 10. The fourth query walks the same path for 2 + 10 + 4 = 16. The total is 9 + 0 + 16 = 25.

Example 3

Input: n = 2, edges = [[0,1,6]], queries = [[1,1,0,4],[2,0,1,0]]
Output: 4
Explanation: The first query names the single edge with its endpoints reversed and sets its weight to 4. The second query returns that weight. The total is 4.