{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"\u003cp\u003e\r\nYou are given a simple connected graph \u003cb\u003eG\u003c/b\u003e with \u003cb\u003eN\u003c/b\u003e vertices and \u003cb\u003eN\u003c/b\u003e edges (a simple graph is an un-directed graph that has no loops and no more than one edge between any two different vertices).\r\nIt is obvious that the graph \u003cb\u003eG\u003c/b\u003e contains exactly one cycle and you can assume that the length of this cycle is odd (there are odd number of vertices in this cycle).\r\nThe vertices are numbered from 1 to \u003cb\u003eN\u003c/b\u003e. Each edge is assigned a corresponding integer weight. \r\nYour mission is to stimulate two types of queries :\r\n\u003cul\u003e\r\n\u003cli\u003e\r\nUpdate query represented by \u003cb\u003ef u v\u003c/b\u003e: change the sign of all the weights of the edges on the shortest path (you can see the definition of shortest path in this problem later on) from vertex \u003cb\u003eu\u003c/b\u003e to vertex \u003cb\u003ev\u003c/b\u003e.\r\n\u003c/li\u003e\r\n\r\n\u003cli\u003e\r\nFind query represented by \u003cb\u003e? u v\u003c/b\u003e: On the shortest path from vertex \u003cb\u003eu\u003c/b\u003e to vertex \u003cb\u003ev\u003c/b\u003e, find the (possibly empty) set of consecutive edges such that the sum of the weights is maximal. In other words, let\u0027s define the shortest path from \u003cb\u003eu\u003c/b\u003e to \u003cb\u003ev\u003c/b\u003e as \u003cb\u003ea_1, a_2, ..., a_k\u003c/b\u003e (where \u003cb\u003ea_1\u003c/b\u003e \u003d \u003cb\u003eu\u003c/b\u003e and \u003cb\u003ea_k\u003c/b\u003e \u003d \u003cb\u003ev\u003c/b\u003e). You have to find \u003cb\u003ea_i\u003c/b\u003e and \u003cb\u003ea_j\u003c/b\u003e such that \u003cb\u003ei\u003c/b\u003e \u003c\u003d \u003cb\u003ej\u003c/b\u003e and the sum of the weights of the edges of the path \u003cb\u003ea_i, a_(i + 1), ..., a_j\u003c/b\u003e is as large as possible. You just have to find that sum.\r\n\u003c/li\u003e\r\n\u003c/ul\u003e\r\n\r\n\u003c/p\u003e \r\n\r\n\u003cp\u003e\r\nThe shortest path between two vertices \u003cb\u003eu\u003c/b\u003e and \u003cb\u003ev\u003c/b\u003e is the path connecting them with the minimal number of vertices. In this problem, it is obvious that there is only one shortest path between any pair of vertices of \u003cb\u003eG\u003c/b\u003e.\r\n\u003c/p\u003e\r\n\r\n\u003ch3\u003eInput\u003c/h3\u003e\r\n\u003cp\u003eThe first line contains an integer \u003cb\u003eN\u003c/b\u003e. Each of the next \u003cb\u003eN\u003c/b\u003e lines represents an edge of the graph with three integers \u003cb\u003eu v c\u003c/b\u003e which mean there is an edge connecting vertices \u003cb\u003eu\u003c/b\u003e and \u003cb\u003ev\u003c/b\u003e and it is has weight \u003cb\u003ec\u003c/b\u003e.\r\nThe next line contains an integer \u003cb\u003eQ\u003c/b\u003e, the number of queries. Each of the next \u003cb\u003eQ\u003c/b\u003e lines represents a query in one of the two forms above.\r\n\u003c/p\u003e\r\n\u003ch3\u003eOutput\u003c/h3\u003e\r\n\u003cp\u003e\r\nFor each \u003cb\u003efind\u003c/b\u003e query, print the result of the query (the maximal sum) on a line.\r\n\u003c/p\u003e\r\n\r\n\u003ch3\u003eConstraints\u003c/h3\u003e\r\n\u003cul\u003e\r\n\u003cli\u003e1 \u0026le; \u003cb\u003eN\u003c/b\u003e \u0026le; 100,000\u003c/li\u003e\r\n\u003cli\u003e1 \u0026le; \u003cb\u003eu\u003c/b\u003e, \u003cb\u003ev\u003c/b\u003e \u0026le; \u003cb\u003eN\u003c/b\u003e\u003c/li\u003e\r\n\u003cli\u003e-10,000 \u0026le; \u003cb\u003ec\u003c/b\u003e \u0026le; 10,000\u003c/li\u003e\r\n\u003cli\u003e1 \u0026le; \u003cb\u003eQ\u003c/b\u003e \u0026le; 100,000\u003c/li\u003e\r\n\u003c/ul\u003e\r\n\r\n\u003ch3\u003eExample\u003c/h3\u003e\r\n\u003cpre\u003e\r\n\u003cb\u003eInput:\u003c/b\u003e\r\n6\r\n1 2 1\r\n2 3 1\r\n3 1 1\r\n2 4 1\r\n4 5 1\r\n3 6 1\r\n3\r\n? 5 6\r\nf 2 3\r\n? 5 6\r\n\r\n\u003cb\u003eOutput:\u003c/b\u003e\r\n4\r\n2\r\n\u003c/pre\u003e\r\n\u003ch3\u003eExplanation\u003c/h3\u003e\r\n\u003cp\u003eThe shortest path from 5 to 6 is 5, 4, 2, 3, 6. All the edges on this path have weight 1 so the answer to the first query is 4. After the second query, the weight of the edge (2, 3) is - 1. The edges on the path 5, 4, 2, 3, 6 have weights 1, 1, -1, 1 respectively. so the answer for the third query is 2.\u003c/p\u003e"}}]}