### brainy_fool's blog

By brainy_fool, 7 weeks ago, Given a tree, find OR of the path between two nodes (u,v). tree, Comments (8)
•  » » » 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))$
•  » » » » » 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[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[i] = v[i]|v[par[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[a]; }; return 0; }