PSHTTR - Editorial

editorial
, , , , ,
1

PROBLEM LINK:

Practice
Contest

Author: Ivan Fekete
Primary Tester: Misha Chorniy
Editorialist: Hussain Kara Fallah

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
TESTER’s solution: Will be found here
EDITORIALIST’s solution: Will be found here

3 Likes
2

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 helped me with implementation )
  4. read this topcoder article
  5. solve spoj lca or this lca problem
  6. finally try to solve this similiar problem

I hope above helps :slight_smile:

9 Likes
3

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

1 Like
4

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)

1 Like
5

practice and contest links are swapped.

6

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.

7

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.

8

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



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.

1 Like
9

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

10

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.


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

Notice:
100 & -100  decimal =      0000000100 binary
11

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


           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
12

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!!

13

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.

14

@deadwing97 please clear my doubt.

15

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


  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.

2 Likes
16

@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:)

17

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