brainy_fool's blog

By brainy_fool, 7 weeks ago,

Given a tree, find OR of the path between two nodes (u,v).

How to do it using binary lifting? (Please share your code if you're able to do it)

• +11

 » 7 weeks ago, # |   0 If you really understand the XOR part i dont know why you have an issue with the OR part. Im pretty sure you just use the exact same logic
•  » » 7 weeks ago, # ^ | ← Rev. 3 →   +3 The XOR of path can be calculated using: Keep xor of every node from the root in xor[] array. xor = xor[u] ^ xor[v] ^ value[lca(u, v)], i guess. Please let me know if I am wrong.
•  » » » 7 weeks ago, # ^ |   +4 Yes, this method works for XOR but not for OR. What works for OR is the binary lifting you mentioned on the blog. If you know $jump[k][i]$ being the OR value of going $2^k$ upwards in the tree starting from $i$, then you can just calculate the path from both u and v to the lca of them in $O(log(n))$
•  » » » » 7 weeks ago, # ^ | ← Rev. 2 →   +3 Hey, Thanks a lot for the reply. Can you please share the code? I am stuck on this problem, and I am new to binary lifting concept. But this was asked in recent test of mine, so I want to know how to do these type of questions.
•  » » » » » 7 weeks ago, # ^ |   0 Here is a code just for what is related to the binary lifting (i didnt read anything and didnt calculate some stuff): Implementation#include #define mp make_pair #define mt make_tuple #define all(x) x.begin(), x.end() #define ff first #define ss second using namespace std; template using matrix = vector>; typedef unsigned int uint; typedef unsigned long long ull; typedef long long ll; typedef pair pii; typedef pair pll; const ll INFL = (1LL<<62)-1; const int INF = (1<<30)-1; const double EPS = 1e-7; const int MOD = 1e9 + 7; const int MAXN = 1e6+1; int main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); int n; vector v(n); // value of i, you read this matrix par(20,vector(n)); // Parent of i, going 2^k upwards from i. Calculate par[0][i] with dfs beforehand. The parent of the root is itself for convinience vector height(n); // also calculate this through dfs matrix jump(20,vector(n)); // OR value of jumping 2^k upwards from i for(int i = 1; i < 20; i++){ for(int j = 0; j < n; j++){ par[i][j] = par[i-1][par[i-1][j]]; } } for(int i = 0; i < n; i++) jump[0][i] = v[i]|v[par[0][i]]; for(int i = 1; i < 20; i++){ for(int j = 0; j < n; j++){ jump[i][j] = jump[i-1][jump[i-1][j]]; } } function lca =[&](int a, int b){ if(height[a] < height[b]){ swap(a,b); } int d = height[a]-height[b]; int resp = v[a]|v[b]; while(d){ // we are jumping from a to equalize the height of a and b, starting from the least significant bit of their difference int jumplenght = __builtin_ctz(d); // this returns the least significant bit in d. for example for the binary value 10100 it returns 2 resp|=jump[jumplenght][a]; a = par[jumplenght][a]; d-=d&-d; // dont know if youre familiar with this. this erases the least significant bit from d. } if(a == b){ return resp; } for(int i = 19; i >= 0; i--){ if(par[i][a] != par[i][b]) resp|=jump[i][a]|jump[i][b], a = par[i][a], b = par[i][b]; } return resp|jump[0][a]; }; return 0; } 
•  » » » » » » 7 weeks ago, # ^ |   0 Thanks a lot. Really appreciate it.
 » 7 weeks ago, # |   +3 Imagine root, u, v are on the same path in order.For the XOR part, cumulativeXOR from u to v is (cumulativeXOR from root to v) ^ (cumulativeXOR from root to u's parent).For the OR part, I'm guessing that you can store the sum of '1's for each bit from root to each node. So if root, u, v are all on the same path in that order, you can ascertain if a bit is set from u to v by taking sum(root to v) — sum(root to u's parent) and checking if it is > 0. So to get the OR from node a to node b, take the cumulativeOR from LCA(a, b) to a (using the cumulative sum technique I just described), and OR with cumulativeOR LCA(a, b) to b. You can do something similar for XOR.Hope that I'm correct and hope that this helps.
 » 7 weeks ago, # |   0 Here is the solution: https://m.youtube.com/watch?v=ub82Xb1C8os