Initially I constructed the given tree but assigned all the edges 0 weight.
Now we should find XOR of all edges from U to V which are less than K.
We sort the queries and the given edges by weight in increasing order(both in the same array).Iterate through each element of the array, if it is a Tree edge node, Assign the value of the weight to edge of the tree. If it is a query node find the XOR of all edges between U and V ,because all the edge weights of your current tree are less than your Query’s K.
I created a vector of nodes where type 0 indicates Tree edge and Type 1 indicates Query.my node looks something like this
class qnode{
public:
int type,u,v,value,qidx,aidx;
bool operator<(const qnode &n) {
if (value != n.value) return value < n.value;
else return type <= n.type;
}
qnode(int a,int b,int c,int d,int e,int f){
type = a;
value = b;
u = c;
v = d;
qidx = e;
aidx = f;
}
};
type denotes wether it is a tree edge or a query ,value denotes the edge weight,U and V are the nodes between which the edge is present,qidx is the query number
So now the problem is simplified to this, Given two types of queries 1)Increment a Edge weight by T 2)what is the XOR of edge weights from U to V.Answer to the second query will be stored in its corresponding query number.
How to solve query 2?, let f(U,V) denotes Xor of all edges between U to V.f(u,v) = f(u,root) ^ f(v,root), because the the portion above lca(u,v) will be cancelled out by the XOR operation and only the part from (u to lca(u,v)) and (v to lca(u,v)) remains.
Using DFS order convert the tree into array and solve it using segment tree.
This is my solution My code
This is my first post so any suggestions are Welcome 