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

  • 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;

    }