{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eThe Lightning Network is a \"Layer 2\" payment protocol that operates on top of a blockchain-based cryptocurrency (like Bitcoin). It enables fast transactions between participating nodes and has been touted as a solution to the Bitcoin scalability problem. It features a peer-to-peer system for making micropayments of cryptocurrency through a network of bidirectional payment channels without delegating custody of funds.\u003c/p\u003e\n\u003cp\u003eIn this problem, we\u0027ll regard the Lightning Network as a tree. And due to the network environment, the cost of these payment channels are changeable. That says, you are given a weighted undirected tree on $n$ vertices and $q$ queries. Each changes the weight of one edge or query the furthest distance of one vertex to another vertex. The distance between two vertices is the sum of the weights on the unique simple path that connects them.\u003c/p\u003e\n\u003ch3\u003eInputFile\u003c/h3\u003e\n\u003cp\u003eThe first line contains an integer $n$ ($1 \\le n \\le 10^5$) --- the number of vertices in the tree.\u003c/p\u003e\n\u003cp\u003eFollowing $n-1$ lines will contain the initial structure of the tree. The $i$-th of these lines contains three space-separated integers $x_i, y_i, w_i$ ($1\\leq x_i, y_i \\leq n, 0\\leq w_i \\leq 10^9$) meaning that initially, there is an edge between vertices $x_i$ and $y_i$ with weight $w_i$. It is guaranteed that these $n-1$ lines describe a tree.\u003c/p\u003e\n\u003cp\u003eThe next line contains an integer $q$ ($1 \\le q \\le 10^5$) --- the number of qeries.Finally, $q$ lines describing queries follow. The $i$-th of these lines contains either \u0027Q $v_i$\u0027 or \u0027C $e_i$ $w_i$\u0027.\u003c/p\u003e\n\u003cul\u003e\n \u003cli\u003eC $e_i$ $w_i$ ($1 \\leq e_i \\leq n-1, 0\\leq w_i \\leq 10^9$), changes the weight of the $e_i$-th edge to $w_i$, or\u003c/li\u003e\n \u003cli\u003eQ $v_i$ ($1 \\leq v_i \\leq n$), query the furthest distance of the vertex $v_i$ to another vertex.\u003c/li\u003e\n\u003c/ul\u003e\n\u003ch3\u003eOutputFile\u003c/h3\u003e\n\u003cp\u003eOutput the query for each query.\u003c/p\u003e"}},{"title":"Sample 1","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e5\n1 2 1\n1 3 1\n2 4 1\n2 5 1\n3\nQ 1\nC 1 2\nQ 2\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2\n3\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003cbr /\u003e"}}]}