# PSHTTR - Editorial

**URL:** <https://discuss.codechef.com/t/pshttr-editorial/15526>\
**Category:** editorial\
**Tags:** data-structure, editorial, july17, medium, pshttr, sorting\
**Created:** [July 15, 2017, 8:10am UTC](https://discuss.codechef.com/t/pshttr-editorial/15526 "2017-07-15T08:10:24Z")\
**Posts on this page:** 19\
**Page:** 1

<div class="post-metadata">

**Author:** ![deadwing97](https://discuss.codechef.com/user_avatar/discuss.codechef.com/deadwing97/32/3653_2.png) [@deadwing97](https://discuss.codechef.com/u/deadwing97)\
**Post date:** [July 15, 2017, 8:10am UTC](https://discuss.codechef.com/t/pshttr-editorial/15526/1 "2017-07-15T08:10:24Z")

</div>

### PROBLEM LINK:

[Practice](https://www.codechef.com/problems/PSHTTR)  
[Contest](https://www.codechef.com/JULY17/problems/PSHTTR)

**Author:** [Ivan Fekete](https://www.codechef.com/users/fekete)  
**Primary Tester:** [Misha Chorniy](https://www.codechef.com/users/mgch)  
**Editorialist:** [Hussain Kara Fallah](https://www.codechef.com/users/deadwing97)

### DIFFICULTY:

Medium

### PREREQUISITES:

Graph Theory,Sorting,Data Structures

### PROBLEM:

Given a rooted weighted tree with **N** nodes and **M** queries of the form **(u , v , K)**. For each query, you must report to **xor** sum of edges which has weight less than or equal to **K** on the path from **u** to **v**.

**N,M ≤ 10^5**

### EXPLANATION:

First of all let’s solve the easier version of this problem. Queries which asks for the xor sum of edges on the path between 2 fixed nodes **(without the restriction of K).**  
Let’s choose an arbitrary root for our tree and call a Depth-First search starting from this node.Let’s maintain a table **S[N]**, such that **Si** denotes the **xor** sum of edges weights starting from the **root** and ending at node **i**. The answer of each query **(u,v)** would be **(Su xor Sv)**. Edges of the chain starting from the root and ending at **LCA(u,v)** (lowest common ancestor) would be excluded because **(V xor V = 0)**.

Now let’s solve our problem. First thing we should take advantage of, is that we can answer our queries offline (reading then processing all queries, after that reporting the answer of each one).  
Each edge weighted **W** must be included in the answer of all queries with **K ≥ W**. For queries with **K \< W** we can assume that this edge’s weight is zero (so it won’t affect the answers).

Let’s sort our queries in ascending order according to their magic numbers **K** , and sort our edges in ascending order according to their weights **W**. Let’s process our queries in ascending order, and maintain a pointer iterating on our sorted edges list. So before processing a query with magic number **K** , we add all edges with **W ≤ K** through our pointer.

Now Let’s discuss adding edges, and how will we get our table S.

Let’s maintain a timer incremented by one every time we visit a new node in our Depth-First-Search, and keep for the **ith** node a variable **sti** (denoting the value of the timer once entering this node),and a variable **eni** denoting the value of the timer after finishing this node’s subtree (before exiting). This is a famous technique called euler tour on tree (dfs order). So we can represent nodes located in the subtree of the **ith** node by interval **[sti , eni]**

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**. That means we should apply the operation

**Si = Si xor V**

for each **i** : **(stv ≤ i ≤ env)**

This can be done using a binary indexed tree, segment tree (with/without) lazy probagation. Since our modification query is done on a segment of array **S** and we are querying the value of only one element we can do the following:

Let’s maintain an array **X** which is all zeros at the beginning. When handling an edge of weight **W** added to the results of nodes in node v subtree.

**X[sti] = X[sti] xor V**

This means that we are adding V to the **xor** sum of all nodes with enterance **timer ≥ stv**

**X[eni + 1] = X[eni + 1] xor V**

This means that we are excluding **V** from the **xor** sum of all elements with entrance **timer \> en[v]** (since it was added in the first operation so doing **xor** again is equivalent to exclusion).

You can notice now that the value of **Si** is:

**Si = X1 xor X2 xor X3 xor X4 xor X5 xor … Xi**

Now we can easily iterate through our queries, and for each one we should make sure that all edges with weight less than or equal to this query magic number are added. After that, each query can be solved in O(log N).

Total complexity **O(N log N + M (log M + log N))**

### AUTHOR’S AND TESTER’S SOLUTIONS:

**AUTHOR’s solution** : Will be found [here](https://s3.amazonaws.com/codechef_shared/download/Solutions/JULY17/Setter/PSHTTR.cpp)  
**TESTER’s solution** : Will be found [here](https://s3.amazonaws.com/codechef_shared/download/Solutions/JULY17/Tester/PSHTTR.cpp)  
**EDITORIALIST’s solution** : Will be found [here](https://s3.amazonaws.com/codechef_shared/download/Solutions/JULY17/Editorialist/PSHTTR.cpp)

---

<div class="post-metadata">

**Author:** ![ak\_mittal006](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@ak\_mittal006](https://discuss.codechef.com/u/ak_mittal006)\
**Post date:** [July 19, 2017, 5:14pm UTC](https://discuss.codechef.com/t/pshttr-editorial/15526/2 "2017-07-19T17:14:55Z")

</div>

Thanks to this problem I learned few new things. For beginners who are facing difficulty solving this (like i did) I recommend following steps -

1. learn dfs
2. learn segment trees (for Range minimum queries) or sparse table
3. Learn about euler array , (this [video](https://www.youtube.com/watch?v=HeeyUZmaZg0) helped me with implementation )
4. read this [topcoder article](https://www.topcoder.com/community/data-science/data-science-tutorials/range-minimum-query-and-lowest-common-ancestor/)
5. solve [spoj lca](http://www.spoj.com/problems/LCA/) or [this lca problem](https://www.codechef.com/problems/TALCA)
6. finally try to solve [this similiar problem](https://www.codechef.com/problems/TAQTREE)

I hope above helps 🙂

---

<div class="post-metadata">

**Author:** ![amit88265](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@amit88265](https://discuss.codechef.com/u/amit88265)\
**Post date:** [July 20, 2017, 2:57pm UTC](https://discuss.codechef.com/t/pshttr-editorial/15526/3 "2017-07-20T14:57:36Z")

</div>

can anyone explain me briefly what is going on above???

---

<div class="post-metadata">

**Author:** ![h\_trap](https://discuss.codechef.com/user_avatar/discuss.codechef.com/h_trap/32/3784_2.png) [@h\_trap](https://discuss.codechef.com/u/h_trap)\
**Post date:** [July 21, 2017, 4:42am UTC](https://discuss.codechef.com/t/pshttr-editorial/15526/4 "2017-07-21T04:42:45Z")

</div>

practice and contest links are swapped.

---

<div class="post-metadata">

**Author:** ![vijju123](https://discuss.codechef.com/user_avatar/discuss.codechef.com/vijju123/32/195207_2.png) [@vijju123](https://discuss.codechef.com/u/vijju123)\
**Post date:** [July 23, 2017, 11:43am UTC](https://discuss.codechef.com/t/pshttr-editorial/15526/5 "2017-07-23T11:43:25Z")

</div>

Can someone explain the get function in Editorial’s solution? Its this-

```
int get(int x){
    int ret = 0;
    while(x > 0){
        ret ^= bit[x];
        x -= x & (-x);
    }
    return ret;
}

```

Can someone explain it? Its my first time coming across this type of implementation, so i cannot backtrack the thought process.

---

<div class="post-metadata">

**Author:** ![vishesh\_345](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@vishesh\_345](https://discuss.codechef.com/u/vishesh_345)\
**Post date:** [July 25, 2017, 11:00pm UTC](https://discuss.codechef.com/t/pshttr-editorial/15526/6 "2017-07-25T23:00:43Z")

</div>

`The answer of each query (u,v) would be (Su xor Sv). Edges of the chain starting from the root and ending at LCA(u,v) (lowest common ancestor) would be excluded because (V xor V = 0).`

Can someone please explain what if root node is in between path of u and v. Now if we take xor S[u] and S[v] then we will take xor of root node twice which will eliminate the contribution of node from the xor since root is taken twice and it vanishes and becomes 0. But that was not intended because root node was a part of the path . Have I got something wrong. Please Help.

---

<div class="post-metadata">

**Author:** ![rajat\_mangla](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@rajat\_mangla](https://discuss.codechef.com/u/rajat_mangla)\
**Post date:** [July 30, 2017, 5:06pm UTC](https://discuss.codechef.com/t/pshttr-editorial/15526/7 "2017-07-30T17:06:21Z")

</div>

in the editorial solution they have binary index tree to store the value…  
i tried to use the soln given using segment tree but it is giving wrong answer …  
can anyone tell me what is wrong in my code?  
[here is the code](http://ideone.com/5lRSww)

---

<div class="post-metadata">

**Author:** ![deadwing97](https://discuss.codechef.com/user_avatar/discuss.codechef.com/deadwing97/32/3653_2.png) [@deadwing97](https://discuss.codechef.com/u/deadwing97)\
**Post date:** [July 20, 2017, 3:23pm UTC](https://discuss.codechef.com/t/pshttr-editorial/15526/8 "2017-07-20T15:23:31Z")

</div>

The editorial is explained in detail. Not understanding a part of it that means that you are missing something you should learn. To solve this problem you should be understanding xor,dfs,dfs order,(Segment tree\BIT)

---

<div class="post-metadata">

**Author:** ![vijju123](https://discuss.codechef.com/user_avatar/discuss.codechef.com/vijju123/32/195207_2.png) [@vijju123](https://discuss.codechef.com/u/vijju123)\
**Post date:** [July 23, 2017, 11:44am UTC](https://discuss.codechef.com/t/pshttr-editorial/15526/9 "2017-07-23T11:44:32Z")

</div>

I think if we add 1-2 more tags in pre-requisite (like euler tour, dfs, segment tree/BIT) then perhaps people will read it after getting through the pre-requisites.

---

<div class="post-metadata">

**Author:** ![john\_smith\_3](https://discuss.codechef.com/user_avatar/discuss.codechef.com/john_smith_3/32/208155_2.png) [@john\_smith\_3](https://discuss.codechef.com/u/john_smith_3)\
**Post date:** [July 23, 2017, 7:32pm UTC](https://discuss.codechef.com/t/pshttr-editorial/15526/10 "2017-07-23T19:32:43Z")

</div>

Read and study the **get()** and **add()** functions at the same time:

```auto

void add(int y , int V){
    while(y <= n){
        bit[y] ^= V;
        y += y & (-y);
    }
}

```

**get()** returns the xor of the **V** values inserted by **add(y, V)** where **y \<= x**.

Note how the expression **x & (-x)** gives the least significant bit of **x** , so that the loop in the **get()** function keeps rounding **x** down to a multiple of larger power of 2, and the loop in **add()** keeps rounding **y** up to a multiple of a larger power of 2.

A similar trick could find the sum of **V** values.

---

<div class="post-metadata">

**Author:** ![vijju123](https://discuss.codechef.com/user_avatar/discuss.codechef.com/vijju123/32/195207_2.png) [@vijju123](https://discuss.codechef.com/u/vijju123)\
**Post date:** [July 23, 2017, 8:15pm UTC](https://discuss.codechef.com/t/pshttr-editorial/15526/11 "2017-07-23T20:15:55Z")

</div>

Thanks john!! I really appreciate your explanation.

Can you just further tell on `x & (-x) gives the least significant bit of x,` ??

I thought that the edge V should be xored in the interval of [st,en] (where st and en are time of entering and leaving that edge’s subtree), i.e. consecutive elements should be xored. Doesnt this depend on numbering of node by some means? I am unable to get it ☹

---

<div class="post-metadata">

**Author:** ![john\_smith\_3](https://discuss.codechef.com/user_avatar/discuss.codechef.com/john_smith_3/32/208155_2.png) [@john\_smith\_3](https://discuss.codechef.com/u/john_smith_3)\
**Post date:** [July 24, 2017, 12:12am UTC](https://discuss.codechef.com/t/pshttr-editorial/15526/12 "2017-07-24T00:12:03Z")

</div>

Most processors use the two’s complement representation of negative numbers. (The C99 standard permits other representations of negative numbers)

To calculate the two’s complement binary representation of -x, write down the binary representation of x, complement each bit, and add one.

For example, 100=64+32+4 decimal, so the 100 decimal is 1100100 binary.

```auto

        100 decimal = ...0001100100 binary
complement each bit ...1110011011
add 1 ...1110011100
       -100 decimal = ...1110011100 binary

Notice:
100 & -100 decimal = 0000000100 binary

```

---

<div class="post-metadata">

**Author:** ![john\_smith\_3](https://discuss.codechef.com/user_avatar/discuss.codechef.com/john_smith_3/32/208155_2.png) [@john\_smith\_3](https://discuss.codechef.com/u/john_smith_3)\
**Post date:** [July 24, 2017, 12:57am UTC](https://discuss.codechef.com/t/pshttr-editorial/15526/13 "2017-07-24T00:57:44Z")

</div>

The nodes are numbered by the depth-first-search process starting at root node, with numbering stored in st[n] (and also, but different, in en[n]).

You are right - edge V is xor-ed in the interval [st,en].

The EDITORIALIST’s solution includes the lines

```auto

           add(st[node] , Q.first);
           add(en[node] + 1 , Q.first);

```

When the corresponding **get(x)** is evaluated,

- if x \< st[node] then Q.first is not included in the big xor
- if st[node] \<= x \<= en[node], then just the first Q.first is included
- if en[node] \< x, then both Q.first ^ Q.first = 0 is included

---

<div class="post-metadata">

**Author:** ![vijju123](https://discuss.codechef.com/user_avatar/discuss.codechef.com/vijju123/32/195207_2.png) [@vijju123](https://discuss.codechef.com/u/vijju123)\
**Post date:** [July 24, 2017, 1:00am UTC](https://discuss.codechef.com/t/pshttr-editorial/15526/14 "2017-07-24T01:00:25Z")

</div>

Thanks a lot man!! I was REALLY clueless about that complement thing in your fist comment. I thought it just inverted some hidden bit in frontmost position (which determined sign).

Your comment clarified everything, Thanks a LOT man!! Really!!

---

<div class="post-metadata">

**Author:** ![vishesh\_345](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@vishesh\_345](https://discuss.codechef.com/u/vishesh_345)\
**Post date:** [July 25, 2017, 11:38pm UTC](https://discuss.codechef.com/t/pshttr-editorial/15526/15 "2017-07-25T23:38:24Z")

</div>

@deadwing97 please clear my doubt.

---

<div class="post-metadata">

**Author:** ![john\_smith\_3](https://discuss.codechef.com/user_avatar/discuss.codechef.com/john_smith_3/32/208155_2.png) [@john\_smith\_3](https://discuss.codechef.com/u/john_smith_3)\
**Post date:** [July 26, 2017, 1:52am UTC](https://discuss.codechef.com/t/pshttr-editorial/15526/16 "2017-07-26T01:52:55Z")

</div>

In the problem, the **V** values are attached to edges between two adjacent nodes.

In the Editorialist’s solution, the values are attached to the node more distant from the root node. There is some logic

```auto

  for(int j = 1 ; j < n ; j++){
     if(st[E[j].first] < st[E[j].second])
         swap(E[j].first , E[j].second);
     sorted.push_back({W[j] , -E[j].first});
  }

```

which swaps the ends of the edge E[j] so that E[j].first is further from the root node than E[j].second.

There is no V associated with the root node,

Hope that makes sense.

---

<div class="post-metadata">

**Author:** ![vishesh\_345](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@vishesh\_345](https://discuss.codechef.com/u/vishesh_345)\
**Post date:** [July 26, 2017, 11:21am UTC](https://discuss.codechef.com/t/pshttr-editorial/15526/17 "2017-07-26T11:21:14Z")

</div>

@john\_smith so i can say that if u to v has to include root it must be the lca of both those nodes(possibly) and in case of that there is no problem because we can take xor as mentioned above without any problem and if root node is the lca then there will be no edge whose xor is to be taken with themselves.Is this correct?  
Thank you for your reply:)

---

<div class="post-metadata">

**Author:** ![gupta\_nitesh](https://discuss.codechef.com/user_avatar/discuss.codechef.com/gupta_nitesh/32/9185_2.png) [@gupta\_nitesh](https://discuss.codechef.com/u/gupta_nitesh)\
**Post date:** [December 19, 2019, 6:51am UTC](https://discuss.codechef.com/t/pshttr-editorial/15526/18 "2019-12-19T06:51:12Z")

</div>

Why this problem is not accepting submissions now?

---

<div class="post-metadata">

**Author:** ![anon55659401](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@anon55659401](https://discuss.codechef.com/u/anon55659401)\
**Post date:** [December 19, 2019, 8:08pm UTC](https://discuss.codechef.com/t/pshttr-editorial/15526/19 "2019-12-19T20:08:15Z")

</div>

This problem can also be solved by storing the sorted edges in the nodes, then just applying binary search to answer online queries, just like we do in the merge-sort-tree

variation ?