First you decompose the tree into paths by the rule presented in the editorial. You need to maintain the father of a path(father[i]) and for each node the path that contains it (path[i]). Now you can use a vector (a[i]) obtained by concatening the previous stored paths and a second vector (pos[i]) where you store the position of a node in the paths vector(a[i]). At the same time you also need a vector (pstart[i]) to save the position of the first node in a path.
Let’s say that you want the minimum value between nodes x and y(presume that every node has a value). You start from y’s path and go from path to father[path] while the paths of x and y are not the same and check for the minimum in:
- [pstart[path[y]],pos[y]] if path[x]!=path[y] ,after this step y=father[path[y]]
- [pos[x],pos[y]] if path[x]==path[y].
The querys can be dealt with by using segment trees on a[i]. Try solving this problem first,because for QTREE6 you need to know lazy update on segment trees.
Complexity: log^2N (logN paths * logN query)
Given a tree with n nodes and m queries,and v[i]-value associated to node i,answer the queries:
- 0 node value -change the value of node to value
- 1 x y -find the minimum value between x and y
INPUT: n,m ;n lines v,v…v[n];n-1 lines x y-edge between x and y;
OUTPUT:solution to 1 x y-type queries;
This is my source: http://ideone.com/HOeNbs