I can proccess queries like "change the value in a vertex", calculate something on a path.
And how to change the value on an edge? I have an idea to store in a vertex edge's weight from the vertex to it's left child (in Splay tree). But there is a problem with changing the root of the tree: after reversing an edge values in the vertexes will become incorrect. Probably I should somehow push value from vertex to it's left child..
(Arc goes to left child, grey vertex is the root)
Could you tell me how to store and change edge's weight correctly using Link-cut tree
Wouldn't it be sufficient to just store the value of an edge in the bottom vertex of that edge? It's just 1 value per edge, and the value of any path that crosses that edge doesn't have that vertex as its topmost one (which can just be subtracted, since there's no other such vertex) will also include the value of that vertex.
As I understood, the main problem is with 'expose' request as it rebuilds the tree and changes 'topmost vertex of an edge'.
Oh, so that's why the link-cut tree was specifically mentioned...
In that case, I don't know. I try to avoid the use of such structures — I try to keep my thinking simple. Maybe you could use some clever sqrt-stuff?
Of course the problem I am trying to solve does not require link-cut structure, it is about the lightest edge on a path queries and it can be solved much more easier. But as I understand Link-Cut tree solves almost all problems about queries on tree, that's why I want to use Link-Cut here.
Can you pleas tell how to solve lightest edge on a path queries ??
I think what he means is that it's easy to solve it offline, if you don't have update queries. You can use static heavy-light decomposition or something like centroid decomposition.
Oh, could you help me to solve lighest edge on a path queries in a dynamic graph?? ...
Can you please provide some link which will help me solve this problem
You have it right here: Use a link-cut tree. There's several resources for that in this thread alone
accesswill not change the parent-child relation of any two nodes in the represented tree, if I'm not mistaken. Since the node depths don't change,accessshould not even change the left/right relation inside an auxiliary tree (although the parent-child relation might change there). So we could identify an edge with its bottom vertex in the represented tree, which happens to be always to be always to the right of it in the auxiliary trees (except when the endpoints are not on the same preferred path, in which case we get the off-by-one situation Xellos mentioned)Yes, access does not change the parent-children relations, but I am talking about evert operation, which swaps left and right children inside a splay tree. Take a look at updated picture
An edge connects two nodes in the represented tree, one of which is the parent and one of which is the child. If you write the edge value into the child you can just do normal range queries in the auxiliary tree. The splay tree operations have little to do with that, they are just a means to compute range aggregations on the path.
So don't think about it in terms of left/right in the auxiliary trees. Two neighboring nodes in the represented tree might not even be directly connected in the auxiliary tree.
As I understood, we have a rooted tree, so we can clearly define vertex values and we don't care about auxiliary tree changes at all.
For example we want to represent such a tree:
Initially all vertices are in different trees. And how to perform link(2, 3, 25) query? I don't know where to write 25
You can only link tree roots: http://en.wikipedia.org/?title=Link/cut_tree#Link. Those don't have an edge value yet, so you can just write the 25 into the newly linked node (in this case, node 3) and the invariant is still fulfilled.
Trees are never restructured if you use link/cut.
2 and 3 both are roots. So you mean that it does not matter where to put 25 and if I put 25 in 2 it will be ok too?
No, you need to put it into the 3. Just put the edge value into the bottom vertex always. It's always possible because every node only has one parent edge.
What do you mean by bottom vertex? For example how can I find bottom vertex in link(1, 2, 10) query?
Or it is possible only if we know all link/cut queries to hang a tree?
By bottom vertex of an edge, I mean the deeper one of the vertices that the edge connects.
link(x,y)assumes thatxis the root of a tree in the represented forest. Thereforexhas no parent edge and if you connect it toy,xwill be the deeper of the two nodes, so it can hold the edge value.Ok, but we need to somehow push the value from a node, because the node must be empty to link it.
Your example doesn't make sense. 1 is not a root so you
link(1,3,20)is not a valid operation. You can only link root nodes. I meantioned this a few times now in this thread, but you seem to skip over most of what I write.You could do
link(2,4,20orlink(2,3,20)orlink(4,1,20)orlink(4,2,20)without problems.With that misunderstanding out of the way, I hope it becomes now clear that your "problematic case" can just not occur in practice.
Maybe you should read the Wikipedia article so we at least agree on a common vocabulary.
1 is not a root, but I can change the root, by evert operation.
The root can be changed by evert(v), which reverses all arcs on the path from v to the previous root.
http://www.cs.princeton.edu/~rwerneck/docs/TW07.pdf
Take a look at 2. Data Structures -> ST-trees
Okay, I didn't know about
evert. However, have a look at page 82 of the document you sent me:"We call the splay-based implementation used in our experiments ST-V. Although it has costs on vertices, it can also represent costs on edges as long as
evertis never called. Supportingevertwith costs on edges requires maintaining additional nodes to represent the edges explicitly. Our implementation of this variant, ST-E, uses ST-V as the underlying data structure."Also have a look at the original ST-Tree paper. They use a reverse bit in the splay tree data structure to implement
evert. They also maintain edge costs.