My solution for PSHTTR

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 :slight_smile:

9 Likes

Hey!
Liked your method.
I think line 152 (ie) build(1,0,n-1); was not needed. Correct me if i am wrong

@hackr32 I have one questions wrt to trees related questions in any contest. When questions mention a tree (just tree and nothing else), then tree necessarily be binary tree always right? It can be any kind of tree. Am I correct?

It can be any tree. Binary tree is just a type of tree.

2 Likes

Wow … Really an impressive solution !

Hi,
I was going through your solution. Could you explain why was this used?
if (u != 0 && parent[u] == v)
low = u;

Regarding adding edges, each edge will link between 2 nodes (u,v) such that u = par[v], this edge’s weight will be added to the xor sum (cumulative xor sum from the root) of all nodes located in the subtree of v.

He is associating every edge with a node which is at higher level.

int low = v;
if (u != 0 && parent[u] == v)
low = u;

Assume v is at a higher level , therefore low = v. Now suppose if u was to be at higher level than v only if parent of u is v. So he is just checking this condition to check which node is at higher level.

Just think a bit. Feel free to ask anything :slight_smile: