Queries on tree again!
All submissions for this problem are available.
You are given a simple connected graph G with N vertices and N edges (a simple graph is an un-directed graph that has no loops and no more than one edge between any two different vertices).
It is obvious that the graph G 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).
The vertices are numbered from 1 to N. Each edge is assigned a corresponding integer weight.
Your mission is to stimulate two types of queries :
- Update query represented by f u v: 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 u to vertex v.
- Find query represented by ? u v: On the shortest path from vertex u to vertex v, find the (possibly empty) set of consecutive edges such that the sum of the weights is maximal. In other words, let's define the shortest path from u to v as a_1, a_2, ..., a_k (where a_1 = u and a_k = v). You have to find a_i and a_j such that i <= j and the sum of the weights of the edges of the path a_i, a_(i + 1), ..., a_j is as large as possible. You just have to find that sum.
The shortest path between two vertices u and v 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 G.
The first line contains an integer N. Each of the next N lines represents an edge of the graph with three integers u v c which mean there is an edge connecting vertices u and v and it is has weight c.
The next line contains an integer Q, the number of queries. Each of the next Q lines represents a query in one of the two forms above.
For each find query, print the result of the query (the maximal sum) on a line.
- 1 ≤ N ≤ 100,000
- 1 ≤ u, v ≤ N
- -10,000 ≤ c ≤ 10,000
- 1 ≤ Q ≤ 100,000
Input: 6 1 2 1 2 3 1 3 1 1 2 4 1 4 5 1 3 6 1 3 ? 5 6 f 2 3 ? 5 6 Output: 4 2
The 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.
|Tags||hard, heavy-light, may13, segment-tree, simple-math, tuananh93|
|Time Limit:||2 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.