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)

Example:

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[1],v[2]…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