We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Data Structures
  3. Advanced
  4. Fibonacci Numbers Tree
  5. Discussions

Fibonacci Numbers Tree

Sort by

recency

|

6 Discussions

|

  • yashpalsinghdeo1
     + 0 comments

    here is hackerrank fibonacci numbers tree solution

  • SHIVAAMANCHI303
     + 0 comments

    include

    using namespace std ;

    define ft first

    define sd second

    define pb push_back

    define all(x) x.begin(),x.end()

    define ull unsigned long long int

    define ui unsigned int

    define ll long long int

    define vi vector

    define vii vector >

    define pii pair

    define vl vector

    define vll vector >

    define pll pair

    define mp make_pair

    define sc(x) scanf("%d",&x)

    define sc2(x,y) scanf("%d%d",&x,&y)

    define sc3(x,y,z) scanf("%d%d%d",&x,&y,&z)

    define scll1(x) scanf("%lld",&x)

    define scll2(x,y) scanf("%lld%lld",&x,&y)

    define scll3(x,y,z) scanf("%lld%lld%lld",&x,&y,&z)

    define pr1(x) printf("%d\n",x)

    define pr2(x,y) printf("%d %d\n",x,y)

    define pr3(x,y,z) printf("%d %d %d\n",x,y,z)

    define prll1(x) printf("%lld\n",x)

    define prll2(x,y) printf("%lld %lld\n",x,y)

    define prll3(x,y,z) printf("%lld %lld %lld\n",x,y,z)

    define pr_vec(v) for(int i=0;i

    define f_in(st) freopen(st,"r",stdin)

    define f_out(st) freopen(st,"w",stdout)

    define fr(i, a, b) for(i=a; i<=b; i++)

    define fb(i, a, b) for(i=a; i>=b; i--)

    include

    include

    define debug( s ) cout << s << "\n"

    const int maxn = 1e5 + 10; const int mod = 1e9 + 7; const int fib0 = 88564505; const int fib1 = 56182730; const int constant = 99999;

    int n, m, ptr, lg, chainNo; vi adj[ maxn ]; int subsize[ maxn ], chainHead[ maxn ], chainInd[ maxn ], posInBase[ maxn ], Base[ maxn ], LCA[ maxn ][22]; int L[ maxn ], in[ maxn ], out[ maxn ], F[ maxn ], I[2][2], T[2][2], vis[ maxn ], heavy[ maxn ];

    void dfs( int u, int par = -1 ) { L[1] = 1; queue Q; stack st; Q.push( 1 ); while( !Q.empty() ) { u = Q.front(); Q.pop(); st.push( u ); subsize[u] = 1; for( auto it: adj[u] ) { LCA[it][0] = u; L[it] = L[u] + 1; Q.push( it ); } } while( !st.empty() ) { u = st.top(); st.pop(); for( auto it: adj[u] ) { subsize[u] += subsize[it]; } } }

    void HLD() { stack st; queue Q;

    Q.push(1);
while( !Q.empty() ) {
    int top = Q.front();
    st.push( top );
    Q.pop();
    for( auto it: adj[top] ) {
        Q.push( it );
    }
}

int i;
fr(i, 1, n) heavy[i] = i;
while( !st.empty() ) {
    int x = st.top(); st.pop();
    int p = LCA[x][0];
    if( heavy[p] == p || subsize[heavy[p]] < subsize[x] ) {
        heavy[p] = x;
    }
}

st.push(1);
++ chainNo;
chainInd[1] = chainNo;
chainHead[chainNo] = 1;
while( !st.empty() ) {
    int top = st.top();
    if( !vis[top] ) {
        Base[++ptr] = top;
        vis[top] = 1;
        if( heavy[top] != top ) {
            st.push( heavy[top] );
            chainInd[heavy[top]] = chainInd[top];
        }
    } else {
        st.pop();
        for( auto it: adj[top] ) {
            if( it != heavy[top] ) {
                ++ chainNo;
                chainInd[it] = chainNo;
                chainHead[ chainNo ] = it;
                st.push( it );
            }
        }
    }
}

fr(i, 1, n) {
    in[Base[i]] = i;
    posInBase[Base[i]] = i;
}

fr(i, 1, n) {
    out[i] = in[i] + subsize[i] - 1;
}

    }

    struct node { int S, Lazy0, Lazy1, F1, F2; node() { S = Lazy0 = Lazy1 = F1 = F2 = 0; } };

    node st[ 4 * maxn ]; class SegmentTree { public:

        void merge(node& a, node& l, node& r) {
        a.S = l.S + r.S;
        if( a.S >= mod ) a.S -= mod;
        a.F1 = l.F1 + r.F1;
        if( a.F1 >= mod ) a.F1 -= mod;
        a.F2 = l.F2 + r.F2;
        if( a.F2 >= mod ) a.F2 -= mod;
    }

    void buildst(int idx,int ss,int se){
        if( ss == se ) {
            st[idx].S = 0; 
            st[idx].Lazy0 = 0;
            st[idx].Lazy1 = 0;
            st[idx].F1 = F[L[Base[ss]]];
            st[idx].F2 = F[L[Base[ss]]+1];
            return;
        }
        int mid=(ss+se) >> 1;
        buildst(2*idx, ss, mid);
        buildst(2*idx+1, mid+1, se);
        merge(st[idx], st[2 * idx], st[2 * idx + 1]);
    }

    void adjust(int idx, int ss, int se) {

        int v = 1LL * st[idx].Lazy0 * st[idx].F1 % mod + 1LL * st[idx].Lazy1 * st[idx].F2 % mod;
        if( v >= mod ) v -= mod;

        st[idx].S += v;
        if( st[idx].S >= mod ) st[idx].S -= mod;

        if( ss != se ) {

            st[2 * idx].Lazy0 += st[idx].Lazy0;
            if( st[2 * idx].Lazy0 >= mod ) st[2 * idx].Lazy0 -= mod;

            st[2 * idx].Lazy1 += st[idx].Lazy1;
            if( st[2 * idx].Lazy1 >= mod ) st[2 * idx].Lazy1 -= mod;

            st[2 * idx + 1].Lazy0 += st[idx].Lazy0;
            if( st[2 * idx + 1].Lazy0 >= mod ) st[2 * idx + 1].Lazy0 -= mod;

            st[2 * idx + 1].Lazy1 += st[idx].Lazy1;
            if( st[2 * idx + 1].Lazy1 >= mod ) st[2 * idx + 1].Lazy1 -= mod;

        }

        st[idx].Lazy0 = st[idx].Lazy1 = 0;
    }

    void update(int idx,int ss,int se,int l,int r, int f0, int f1){
        if( st[idx].Lazy1 || st[idx].Lazy0 ) {
            adjust(idx, ss, se);            
        }
        if( l > se || r < ss ) return;
        if(l <= ss && se <= r ){
                st[idx].Lazy0 = f0;
                st[idx].Lazy1 = f1;
                adjust(idx, ss, se);
                return;
        }
        int mid = ( ss + se ) >> 1;
        update(2*idx, ss, mid, l, r, f0, f1);
        update(2*idx+1, mid+1, se, l, r, f0, f1);
        merge(st[idx], st[2 * idx], st[2 * idx + 1]);
    }

    int query(int idx,int ss,int se,int l,int r){
        if( st[idx].Lazy1 || st[idx].Lazy0 ) {
            adjust(idx, ss, se);            
        }
        if( l > se || r < ss || l > r ) return 0;
        if( l <= ss && se <= r ) return st[idx].S;
        int mid = ( ss + se ) >> 1;
        int L = query(2*idx, ss, mid, l, r);
        int R = query(2*idx+1, mid+1, se, l, r);
        L += R; if( L >= mod ) L-= mod;
        return L;
    }

    };

    SegmentTree SegTree; int query_up(int u, int v) { int uchain, vchain = chainInd[v]; int ans = 0; while(1) { uchain = chainInd[u]; if(uchain == vchain) { ans += SegTree.query(1, 1, n, posInBase[v], posInBase[u]); if( ans >= mod ) ans -= mod; break; } // do query from u chain’s head to u ans += SegTree.query(1, 1, n, posInBase[chainHead[uchain]], posInBase[u]); if( ans >= mod ) ans -= mod; u = chainHead[uchain]; // promote u to chain’s head and then to its parent // update answer u = LCA[u][0]; } return ans; }

    void ConstructLCA() { lg = ceil(log2(n)); memset(LCA, -1, sizeof LCA); dfs(1, -1); int i, j; fr(i, 1, lg) { fr(j, 1, n) { if(LCA[j][i-1] != -1) { LCA[j][i] = LCA[LCA[j][i-1]][i-1]; } } } }

    int getLca(int x, int y) { if(L[x] < L[y]) swap(x, y); for(int i=lg; i>=0; i--) { if( LCA[x][i] != -1 && L[LCA[x][i]] >= L[y] ) x = LCA[x][i]; } if( x == y ) return x; for(int i=lg; i>=0; i--) { if( LCA[x][i] != -1 && LCA[x][i] != LCA[y][i] ) x = LCA[x][i] , y = LCA[y][i]; } return LCA[x][0]; }

    void reset() { I[0][0] = 1; I[0][1] = 0; I[1][0] = 0; I[1][1] = 1;

    T[0][0] = 0;
T[0][1] = 1;
T[1][0] = 1;
T[1][1] = 1;

    }

    void mult(int A[2][2], int B[2][2]) { int temp[2][2]; int i, j, k; fr(i, 0, 1) { fr(j, 0, 1) { temp[i][j] = 0; fr(k, 0, 1) { temp[i][j] += 1LL * A[i][k] * B[k][j] % mod; if( temp[i][j] >= mod ) temp[i][j] -= mod; } } } fr(i, 0, 1) { fr(j, 0, 1) { A[i][j] = temp[i][j]; } } }

    void fibo( ll x ) { reset(); while( x ) { if( x % 2 ) mult(I, T); x /= 2; mult(T, T); } }

    int main() {

    // f_in( "in15.txt" );
// f_out( "out15.txt" );

sc2(n, m);

int i;
fr(i, 2, n) {
    int p; sc( p );
    adj[p].pb( i );
}

ConstructLCA();
HLD();

F[1] = 1;
fr(i, 2, 100005) {
    F[i] = F[i-1] + F[i-2];
    if( F[i] >= mod ) F[i] -= mod;
}
SegTree.buildst(1, 1, n);
int u, v;
ll k;
while( m -- ) {
    char type; cin >> type;
    if( type == 'U' ) {
        sc(u); scll1(k);
        k -= L[u];
        k += constant;
        fibo( k );
        int f0, f1;
        f0 = 1LL * I[0][0] * fib0 % mod + 1LL * I[0][1] * fib1 % mod; if( f0 >= mod ) f0 -= mod; 
        f1 = 1LL * I[1][0] * fib0 % mod + 1LL * I[1][1] * fib1 % mod; if( f1 >= mod ) f1 -= mod;
        SegTree.update(1, 1, n, in[u], out[u], f0, f1);
    } else {
        sc2(u, v);
        int lca, ans;
        lca = getLca(u, v);
        ans = 0;
        ans += query_up(u, lca);
        if( ans >= mod ) ans -= mod;
        ans += query_up(v, lca);
        if( ans >= mod ) ans -= mod;
        ans -= SegTree.query(1, 1, n, posInBase[lca], posInBase[lca]);
        if( ans < 0 ) ans += mod;
        pr1( ans );
    }
}
return 0;

    }

  • mrussotto
     + 0 comments

    This can be done (at least in C) with sqrt(n) decomposition instead of HLD, but it's close and micro-optimizations count.

  • kcampos0101
     + 1 comment

    I'm confused about the way the example tree is built. Shouldn't the left-most leaf be the fourth node?

  • phaneendra_4530
     + 1 comment

    somehow my output isnt right

    import java.io.; import java.util.; import java.text.; import java.math.; import java.util.regex.*;

    public class Solution {

    public static void main(String[] args) {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
   Scanner scan = new Scanner(System.in);
    Solution s = new Solution();
    long n = scan.nextInt();
    long m = scan.nextInt();
    final double modConst = Math.pow(10,9)+7;
    Node node = null;
    Node root = null;
    int id = 1;
    for(int i=0;i<n-1;i++){
        if(node == null){
            node = new Node(scan.nextLong());
            node.id = ++id;
            root = node;
        } else if( node.left == null) {
            node.left = new Node(scan.nextLong());
            node.left.parent = node;
            node.left.id = ++id;
        } else if( node.right == null) {
            node.right = new Node(scan.nextLong());
            node.right.id = ++id;
            node.right.parent = node;
            node = node.left;
        }
    }
    if(node.left == null){
        node.left = new Node(0);
        node.left.parent = node;
        node.left.id = 1;
    } else if (node.right == null){
        node.right = new Node(0);
        node.right.parent = node;
        node.right.id = 1;
    }
    List<List<String>> queries = new ArrayList<List<String>>();
    List<String> query = null;
    for( int i=0;i<m;i++){
        query = new ArrayList<String>();
        for(int j = 0; j < 3;j++){
           query.add(scan.next());
        }
        queries.add(query);
    }
    long nNum,rNum, sum = 0;
    for(List<String> task : queries) {
        nNum = Long.parseLong(task.get(1));
        rNum = Long.parseLong(task.get(2));
       if(task.get(0).equalsIgnoreCase("U")){
           //s.printTree(root);
           s.updateOperation(nNum,rNum,root);
          // s.printTree(root);
       } else {
          s.printTree(root);
         sum = s.queryOperation(nNum,rNum,root);
         System.out.println( sum % modConst );

         System.out.println("\n\n\n");

       }
    }

   // System.out.println(s.fetchTreeSize(root));

}

private Node findNode(long nodeNumber, Node rootNode){
     if(rootNode == null){
        return null;
    } 

    if(rootNode.id != nodeNumber){
        findNode(nodeNumber,rootNode.left );
        findNode(nodeNumber,rootNode.right );
        return rootNode;
    } else {
        return rootNode;
    }
}

private long queryOperation(long xNum,long yNum,Node rootNode){
    Node yNode = findNode(yNum, rootNode);
    long sum = 0;
    System.out.println("yNode Val:"+yNode.value+" yNum:"+yNum);
    while(yNode.parent != null && yNode.parent.id != xNum){
        sum = sum + yNode.value;

        if(yNode.parent == null){
            break;
        }
        yNode = yNode.parent;
    }
    return sum ;

}

private void updateOperation(long nodeNumber, long kfibo, Node rootNode) {

      rootNode = findNode(nodeNumber,rootNode);
      long treeElements = fetchTreeSize(rootNode);
      UpdateTree(rootNode,kfibo,0);

}

private void printTree(Node rootNode){
    if(rootNode == null ) {
        return;
    }

    printTree(rootNode.left);
    System.out.println("id :"+rootNode.id+" value :"+rootNode.value);
     printTree(rootNode.right);
}

private void UpdateTree(Node updNode, long item,int level){
    if(updNode == null){
        return;
    }
    updNode.addValue(fetchFibonaciiValue(item+level));
    UpdateTree(updNode.left,item,++level);
    UpdateTree(updNode.right,item,level);
}


private long fetchFibonaciiValue(long element){
    if(element == 1 || element == 2) {
        return 1;
    } else if(element < 1){
        return 0;
    } else {
        return fetchFibonaciiValue(element-1) + fetchFibonaciiValue(element -2);
    }
}

private long fetchTreeSize(Node rootNode){
    if(rootNode == null){
        return 0;
    } else {
        return 1 + fetchTreeSize(rootNode.left)+fetchTreeSize(rootNode.right);
    }
}

    } class Node { Node left = null; Node right = null; Node parent = null; long value = 0; long id = 0; Node(long val) { this.value = val; this.left = null; this.right = null; }

    public void addValue(long p) {
    this.value = value + p;
}

    }